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.

The triangle-free graphs with the most edges for their vertices are balanced complete bipartite graphs. Many triangle-free graphs are not bipartite, for example any cycle graph C_n for odd n > 3.

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.

Triangle finding problem

The triangle finding or triangle detection 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 ${\displaystyle m}$ edges is triangle-free in time ${\displaystyle {\tilde {O}}{\bigl (}m^{2\omega /(\omega +1)}{\bigr )}}$ where the ${\displaystyle {\tilde {O}}}$ hides sub-polynomial factors. Here ${\displaystyle \omega }$ is the exponent of fast matrix multiplication;^[1] ${\displaystyle \omega <2.372}$ from which it follows that triangle detection can be solved in time ${\displaystyle O(m^{1.407})}$. Another approach is to find the trace of A³, 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 again relies on matrix multiplication, since it gets the time complexity down to ${\displaystyle O(n^{\omega })}$, where ${\displaystyle n}$ is the number of vertices.

Even if matrix multiplication algorithms with time ${\displaystyle O(n^{2})}$ were discovered, the best time bounds that could be hoped for from these approaches are ${\displaystyle O(m^{4/3})}$ or ${\displaystyle O(n^{2})}$. In fine-grained complexity, the sparse triangle hypothesis is an unproven computational hardness assumption asserting that no time bound of the form ${\displaystyle O(m^{4/3-\delta })}$ is possible, for any ${\displaystyle \delta >0}$, regardness of what algorithmic techniques are used. It, and the corresponding dense triangle hypothesis that no time bound of the form ${\displaystyle O(n^{\omega -\delta })}$ is possible, imply lower bounds for several other computational problems in combinatorial optimization and computational geometry.^[2]

As Imrich, Klavžar & Mulder (1999) showed, 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 Θ(n²). However, for quantum algorithms, the best known lower bound is Ω(n), but the best known algorithm is O(n^5/4).^[3]

Independence number and Ramsey theory

An independent set of ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ vertices (where ${\displaystyle \lfloor \cdot \rfloor }$ is the floor function) in an n-vertex triangle-free graph is easy to find: either there is a vertex with at least ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ neighbors (in which case those neighbors are an independent set) or all vertices have strictly less than ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ neighbors (in which case any maximal independent set must have at least ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ vertices).^[4] This bound can be tightened slightly: in every triangle-free graph there exists an independent set of ${\displaystyle \Omega ({\sqrt {n\log n}})}$ vertices, and in some triangle-free graphs every independent set has ${\displaystyle O({\sqrt {n\log n}})}$ vertices.^[5] One way to generate triangle-free graphs in which all independent sets are small is the triangle-free process^[6] 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 ${\displaystyle O({\sqrt {n\log n}})}$. It is also possible to find regular graphs with the same properties.^[7]

These results may also be interpreted as giving asymptotic bounds on the Ramsey numbers R(3,t) of the form ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$: if the edges of a complete graph on ${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$ 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.

Coloring triangle-free graphs

The Grötzsch graph is a triangle-free graph that cannot be colored with fewer than four colors

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.^[8] However, nonplanar triangle-free graphs may require many more than three colors.

The first construction of triangle free graphs with arbitrarily high chromatic number is due to Tutte (writing as Blanche Descartes^[9]). This construction started from the graph with a single vertex say ${\displaystyle G_{1}}$ and inductively constructed ${\displaystyle G_{k+1}}$ from ${\displaystyle G_{k}}$ as follows: let ${\displaystyle G_{k}}$ have ${\displaystyle n}$ vertices, then take a set ${\displaystyle Y}$ of ${\displaystyle k(n-1)+1}$ vertices and for each subset ${\displaystyle X}$ of ${\displaystyle Y}$ of size ${\displaystyle n}$ add a disjoint copy of ${\displaystyle G_{k}}$ and join it to ${\displaystyle X}$ with a matching. From the pigeonhole principle it follows inductively that ${\displaystyle G_{k+1}}$ is not ${\displaystyle k}$ colourable, since at least one of the sets ${\displaystyle X}$ must be coloured monochromatically if we are only allowed to use k colours. 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.^[10] Gimbel & Thomassen (2000) and Nilli (2000) showed that the number of colors needed to color any m-edge triangle-free graph is

${\displaystyle 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, 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 Hajnal^[11] found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)n for any ε > 0.

See also

• Andrásfai graph, a family of triangle-free circulant graphs with diameter two
• Henson graph, an infinite triangle-free graph that contains all finite triangle-free graphs as induced subgraphs
• Shift graph, a family of triangle-free graphs with arbitrarily high chromatic number
• The Kneser graph ${\displaystyle KG_{3k-1,k}}$ is triangle free and has chromatic number ${\displaystyle k+1}$
• Monochromatic triangle problem, the problem of partitioning the edges of a given graph into two triangle-free graphs
• Ruzsa–Szemerédi problem, on graphs in which every edge belongs to exactly one triangle

References

Notes

1. Alon, Yuster & Zwick (1994).
2. Abboud et al. (2022); Chan (2023); Jin & Xu (2023)
3. Le Gall (2014), improving previous algorithms by Lee, Magniez & Santha (2013) and Belovs (2012).
4. Boppana & Halldórsson (1992) p. 184, based on an idea from an earlier coloring approximation algorithm of Avi Wigderson.
5. Kim (1995).
6. Erdős, Suen & Winkler (1995); Bohman (2009).
7. Alon, Ben-Shimon & Krivelevich (2010).
8. Grötzsch (1959); Thomassen (1994)).
9. Descartes (1947); Descartes (1954)
10. Chvátal (1974).
11. see Erdős & Simonovits (1973).

Sources

• Abboud, Amir; Bringmann, Karl; Khoury, Seri; Zamir, Or (2022), "Hardness of approximation in P via short cycle removal: cycle detection, distance oracles, and beyond", in Leonardi, Stefano; Gupta, Anupam (eds.), STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, {ACM}, pp. 1487–1500, arXiv:2204.10465, doi:10.1145/3519935.3520066, S2CID 248366492
• Alon, Noga; Ben-Shimon, Sonny; Krivelevich, Michael (2010), "A note on regular Ramsey graphs", Journal of Graph Theory, 64 (3): 244–249, arXiv:0812.2386, doi:10.1002/jgt.20453, MR 2674496, S2CID 1784886.
• 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" (PDF), Discrete Mathematics, 8 (3): 205–218, doi:10.1016/0012-365X(74)90133-2.
• Belovs, Aleksandrs (2012), "Span programs for functions with constant-sized 1-certificates", Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12), New York, NY, USA: ACM, pp. 77–84, arXiv:1105.4024, doi:10.1145/2213977.2213985, ISBN 978-1-4503-1245-5, S2CID 18771464.
• Bohman, Tom (2009), "The triangle-free process", Advances in Mathematics, 221 (5): 1653–1677, arXiv:0806.4375, doi:10.1016/j.aim.2009.02.018, MR 2522430, S2CID 17701040.
• 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, S2CID 123335474.
• Brandt, S.; Thomassé, S. (2006), Dense triangle-free graphs are four-colorable: a solution to the Erdős–Simonovits problem (PDF).
• Chan, Timothy M. (2023), "Finding triangles and other small subgraphs in geometric intersection graphs", in Bansal, Nikhil; Nagarajan, Viswanath (eds.), Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, {SIAM}, pp. 1777–1805, arXiv:2211.05345, doi:10.1137/1.9781611977554.ch68
• Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803.
• Descartes, Blanche (April 1947), "A three colour problem", Eureka, 21.
• Descartes, Blanche (1954), "Solution to Advanced Problem no. 4526", Amer. Math. Monthly, 61: 352.
• 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, vol. 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), vol. 62, pp. 89–99, doi:10.1016/S0304-0208(08)73552-7.
• 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, S2CID 14364050.
• 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, Ce; Xu, Yinzhan (2023), "Removing additive structure in 3SUM-based reductions", in Saha, Barna; Servedio, Rocco A. (eds.), Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, {ACM}, pp. 405–418, arXiv:2211.07048, doi:10.1145/3564246.3585157, S2CID 253510334
• 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 ${\displaystyle R(3,t)}$ has order of magnitude ${\displaystyle {\tfrac {t^{2}}{\log t}}}$", Random Structures and Algorithms, 7 (3): 173–207, doi:10.1002/rsa.3240070302, S2CID 16658980.
• Le Gall, François (October 2014), "Improved quantum algorithm for triangle finding via combinatorial arguments", Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), IEEE, pp. 216–225, arXiv:1407.0085, doi:10.1109/focs.2014.31, ISBN 978-1-4799-6517-5, S2CID 5760574.
• Lee, Troy; Magniez, Frédéric; Santha, Miklos (2013), "Improved quantum query algorithms for triangle finding and associativity testing", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013): New Orleans, Louisiana, USA, January 6–8, 2013, Association for Computing Machinery (ACM); Society for Industrial and Applied Mathematics (SIAM), pp. 1486–1502, ISBN 978-1-611972-51-1.
• Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Math., 3 (2): 161–162, doi:10.4064/cm-3-2-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.

External links

• "Graphclass: triangle-free", Information System on Graph Classes and their Inclusions