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.
The triangle finding problem is the problem of determining whether a graph is triangle-free or not. When the graph does contain a triangle, algorithms are often required to output three vertices which form a triangle in the graph.
It is possible to test whether a graph with m edges is triangle-free in time O(m1.41).1 Another approach is to find the trace of A3, where A is the adjacency matrix of the graph. The trace is zero if and only if the graph is triangle-free. For dense graphs, it is more efficient to use this simple algorithm which relies on matrix multiplication, since it gets the time complexity down to O(n2.373), where n is the number of vertices.
As Imrich, Klavžar & Mulder (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.
The decision tree complexity or query complexity of the problem, where the queries are to an oracle which stores the adjacency matrix of a graph, is Θ(n2). However, for quantum algorithms, the best known lower bound is Ω(n), but the best known algorithm is O(n1.29) due to Belovs (2011).
An independent set of √n vertices in an n-vertex triangle-free graph is easy to find: either there is a vertex with greater than √n neighbors (in which case those neighbors are an independent set) or all vertices have fewer than √n neighbors (in which case any maximal independent set must have at least √n vertices).2 This bound can be tightened slightly: in every triangle-free graph there exists an independent set of vertices, and in some triangle-free graphs every independent set has vertices.3 One way to generate triangle-free graphs in which all independent sets are small is the triangle-free process4 in which one generates a maximal triangle-free graph by repeatedly adding randomly chosen edges that do not complete a triangle. With high probability, this process produces a graph with independence number . It is also possible to find regular graphs with the same properties.5
These results may also be interpreted as giving asymptotic bounds on the Ramsey numbers R(3,t) of the form : if the edges of a complete graph on vertices are colored red and blue, then either the red graph contains a triangle or, if it is triangle-free, then it must have an independent set of size t corresponding to a clique of the same size in the blue graph.
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.6 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.7 Gimbel &Thomassen & (2000) and Nilli (2000) showed that the number of colors needed to color any m-edge triangle-free graph is
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, Erdős & Sós (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, Erdős & 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, because Häggkvist's graph requires four colors and has exactly 10n/29 neighbors per vertex. Finally, Brandt & Thomassé (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 Hajnal8 found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)n for any ε > 0.
- Monochromatic triangle problem, the problem of partitioning the edges of a given graph into two triangle-free graphs
- Alon, Yuster & Zwick (1994).
- Boppana & Halldórsson (1992) p. 184, based on an idea from an earlier coloring approximation algorithm of Avi Wigderson.
- Kim (1995).
- Erdős, Suen & Winkler (1995); Bohman (2008)
- Alon, Ben-Shimon & Krivelevich (2008).
- Grötzsch (1959); Thomassen (1994)).
- Chvátal (1974).
- see Erdős & Simonovits (1973).
- Alon, N.; Ben-Shimon, S.; Krivelevich, M. (2008). "A note on regular Ramsey graphs". arXiv:0812.2386..
- Alon, N.; Yuster, R.; Zwick, U. (1994), "Finding and counting given length cycles", Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 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 (3): 205–218, doi:10.1016/0012-365X(74)90133-2.
- Bohman, T. (2008). "The triangle-free process". arXiv:0806.4375..
- Boppana, Ravi; Halldórsson, Magnús M. (1992), "Approximating maximum independent sets by excluding subgraphs", BIT 32 (2): 180–196, doi:10.1007/BF01994876, MR 1172185.
- Brandt, S.; Thomassé, S. (2006), 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 Journal on Computing 14 (1): 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), Lecture Notes in Mathematics 406, Springer-Verlag, pp. 243–246.
- Erdős, P.; Simonovits, M. (1973), "On a valence problem in extremal graph theory", Discrete Mathematics 5 (4): 323–334, doi:10.1016/0012-365X(73)90126-X.
- Erdős, P.; Suen, S.; Winkler, P. (1995), "On the size of a random maximal graph", Random Structures and Algorithms 6 (2–3): 309–318, doi:10.1002/rsa.3240060217.
- Gimbel, John; Thomassen, Carsten (2000), "Coloring triangle-free graphs with fixed size", Discrete Mathematics 219 (1-3): 275–277, doi:10.1016/S0012-365X(00)00087-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), pp. 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, doi:10.1137/S0895480197323494, MR 1666073.
- Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing 7 (4): 413–423, doi:10.1137/0207033.
- Jin, G. (1995), "Triangle-free four-chromatic graphs", Discrete Mathematics 145 (1-3): 151–170, doi:10.1016/0012-365X(94)00063-O.
- Kim, J. H. (1995), "The Ramsey number has order of magnitude ", Random Structures and Algorithms (3 ed.) 7: 173–207.
- Magniez, Frederic; Santha, Miklos; Szegedy, Mario (2003). "Quantum Algorithms for the Triangle Problem". arXiv:quant-ph/0310134..
- 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.
- Thomassen, C. (1994), "Grötzsch's 3-color theorem", Journal of Combinatorial Theory, Series B 62 (2): 268–279, doi:10.1006/jctb.1994.1069.
- Belovs, Aleksandrs (2011). "Span Programs for Functions with Constant-Sized 1-certificates". arXiv:1105.4024..