Triangle-free graph

From Wikipedia, the free encyclopedia

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.

[edit] 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}} \right)$

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 2n/5 neighbors must be bipartite. This is the best possible result of this type, as the 5-cycle requires three colors but has exactly 2n/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 10n/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.

[edit] References

Alon, N.; Yuster, R.; Zwick, U. (1994). "Finding and counting given length cycles". Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands: 354–364.

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

Brandt, S.; Thomassé, S.. Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem.

Chiba, N.; Nishizeki, T. (1985). "Arboricity and subgraph listing algorithms". SIAM J. Comput. 14: 210–223. doi:10.1137/0214017.

Chvátal, Vašek (1974). "The minimality of the Mycielski graph". Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973): 243–246, Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag.

Erdős, P.; Simonovits, M. (1973). "On a valence problem in extremal graph theory". Discrete Mathematics 5: 323–334. doi:10.1016/0012-365X(73)90126-X.

Grötzsch, H. (1959). "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel". Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8: 109–120.

Häggkvist, R. (1981). "Odd cycles of specified length in nonbipartite graphs". Graph Theory (Cambridge, 1981): 89–99.

Imrich, Wilfried; Klavžar, Sandi & Mulder, Henry Martyn (1999), “Median graphs and triangle-free graphs”, SIAM Journal on Discrete Mathematics 12 (1): 111–118, MR 1666073, DOI 10.1137/S0895480197323494 .

Itai, A.; Rodeh, M. (1978). "Finding a minimum circuit in a graph". SIAM J. Comput. 7: 413–423. doi:10.1137/0207033.

Jin, G. (1995). "Triangle-free four-chromatic graphs". Discrete Mathematics 145: 151–170. doi:10.1016/0012-365X(94)00063-O.

Mycielski, J. (1955). "Sur le coloriage des graphes". Colloq. Math. 3: 161–162.

Nilli, A. (2000). "Triangle-free graphs with large chromatic numbers". Discrete Mathematics 211 (1–3): 261–262. doi:10.1016/S0012-365X(99)00109-0.

Shearer, J. B. (1983). "Note on the independence number of triangle-free graphs". Discrete Mathematics 46 (1): 83–87. doi:10.1016/0012-365X(83)90273-X.