Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

By Turán's theorem, the "n"-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible.

It is possible to test whether a graph with "m" edges is triangle-free in time O("m"^1.41) (Alon et al. 1994). As Imrich et al. (1999) show, triangle-free graph recognition is equivalent in complexity to median graph recognition; however, the current best algorithms for median graph recognition use triangle detection as a subroutine rather than vice versa.

Coloring triangle-free graphs

Much research about triangle-free graphs has focused on graph coloring. Every bipartite graph (that is, every 2-colorable graph) is triangle-free, and Grötzsch's theorem states that every triangle-free planar graph may be 3-colored (Grötzsch 1959; Thomassen 1994). However, nonplanar triangle-free graphs may require many more than three colors.

Mycielski (1955) defined a construction, now called the Mycielskian, for forming a new triangle-free graph from another triangle-free graph. If a graph has chromatic number "k", its Mycielskian has chromatic number "k"+1, so this construction may be used to show that arbitrarily large numbers of colors may be needed to color nonplanar triangle-free graphs. In particular the Grötzsch graph, an 11-vertex graph formed by repeated application of Mycielski's construction, is a triangle-free graph that cannot be colored with fewer than four colors, and is the smallest graph with this property (Chvátal 1974). Nilli (2000) showed that the number of colors needed to color any "m"-edge triangle-free graph is:$O\; left(frac\{m^\{1/3\{(log\; m)^\{2/3\; ight)$and that there exist triangle-free graphs that have chromatic numbers proportional to this bound.

There have also been several results relating coloring to minimum degree in triangle-free graphs.Andrásfai et al (1974) proved that any "n"-vertex triangle-free graph in which each vertex has more than 2"n"/5 neighbors must be bipartite.This is the best possible result of this type, as the 5-cycle requires three colors but has exactly 2"n"/5 neighbors per vertex.Motivated by this result, Paul Erdős and M. Simonovits (1973) conjectured that any "n"-vertex triangle-free graph in which each vertex has at least "n"/3 neighbors can be colored with only three colors; however, Häggkvist (1981) disproved this conjecture by finding a counterexample in which each vertex of the Grötzsch graph is replaced by an independent set of a carefully chosen size. Jin (1995) showed that any "n"-vertex triangle-free graph in which each vertex has more than 10"n"/29 neighbors must be 3-colorable; this is the best possible result of this type. Finally, Brandt and Thomassé (unpublished as of 2006) proved that any "n"-vertex triangle-free graph in which each vertex has more than "n"/3 neighbors must be 4-colorable. Additional results of this type are not possible, as Hajnal (see Erdős and Simonovits 1973) found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3-ε)"n" for any ε > 0.

References

*cite conference
author = Alon, N.; Yuster, R.; Zwick, U.
title = Finding and counting given length cycles
booktitle = Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands
pages = 354–364
date = 1994

*cite journal
author = Andrásfai, B.; Erdős, P.; Sós, V. T.
title = On the connection between chromatic number, maximal clique and minimal degree of a graph
journal = Discrete Mathematics
volume = 8
year = 1974
pages = 205–218
doi = 10.1016/0012-365X(74)90133-2

*cite web
author = Brandt, S.; Thomassé, S.
title = Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem
url = http://www.lirmm.fr/~thomasse/liste/vega11.pdf

*cite journal
author = Chiba, N.; Nishizeki, T.
title = Arboricity and subgraph listing algorithms
journal = SIAM J. Comput.
volume = 14
year = 1985
pages = 210–223
doi = 10.1137/0214017

*cite conference
author = Chvátal, Vašek
title = The minimality of the Mycielski graph
booktitle = Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973)
date = 1974
pages = 243–246
publisher = Lecture Notes in Mathematics, Vol. 406, Springer-Verlag
location = Berlin

*cite journal
author = Erdős, P.; Simonovits, M.
title = On a valence problem in extremal graph theory
journal = Discrete Mathematics
volume = 5
year = 1973
pages = 323–334
doi = 10.1016/0012-365X(73)90126-X

*cite journal
author = Grötzsch, H.
title = Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel
journal = Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe
volume = 8
year = 1959
pages = 109–120

*cite conference
author = Häggkvist, R.
title = Odd cycles of specified length in nonbipartite graphs
booktitle = Graph Theory (Cambridge, 1981)
date = 1981
pages = 89–99

*citation
last1 = Imrich | first1 = Wilfried | last2 = Klavžar | first2 = Sandi
last3 = Mulder | first3 = Henry Martyn
title = Median graphs and triangle-free graphs
journal = SIAM Journal on Discrete Mathematics
volume = 12 | issue = 1 | pages = 111–118 | year = 1999
id = MathSciNet | id = 1666073
doi = 10.1137/S0895480197323494.

*cite journal
title = Finding a minimum circuit in a graph
author = Itai, A.; Rodeh, M.
journal = SIAM J. Comput.
volume = 7
year = 1978
pages = 413–423
doi = 10.1137/0207033

*cite journal
author = Jin, G.
title = Triangle-free four-chromatic graphs
journal = Discrete Mathematics
volume = 145
year = 1995
pages = 151–170
doi = 10.1016/0012-365X(94)00063-O

*cite journal
author = Mycielski, J.
title = Sur le coloriage des graphes
journal = Colloq. Math.
volume = 3
year = 1955
pages = 161–162

*cite journal
author = Nilli, A.
title = Triangle-free graphs with large chromatic numbers
journal = Discrete Mathematics
volume = 211
year = 2000
issue = 1–3
pages = 261–262
doi = 10.1016/S0012-365X(99)00109-0

*cite journal
title = Note on the independence number of triangle-free graphs
author = Shearer, J. B.
journal = Discrete Mathematics
volume = 46
issue = 1
pages = 83–87
year = 1983
doi = 10.1016/0012-365X(83)90273-X

*cite journal
author = Thomassen, C.
title = Grötzsch's 3-color theorem
journal = Journal of Combinatorial Theory, Series B
volume = 62
year = 1994
pages = 268–279
doi = 10.1006/jctb.1994.1069

External links

* cite web | url=http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_371.html | title=triangle-free
work = [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions]