{{Short description|Graph without triples of adjacent vertices}} 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.

[[File:Biclique K 5 5.svg|thumb|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''<sub>''n''</sub> for odd&nbsp;''n''&nbsp;>&nbsp;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 <math>m</math> edges is triangle-free in time <math>\tilde O\bigl(m^{2\omega/(\omega+1)}\bigr)</math> where the <math>\tilde O</math> hides sub-polynomial factors. Here <math>\omega</math> is the exponent of fast matrix multiplication;{{sfnp|Alon|Yuster|Zwick|1994}} <math>\omega<2.372</math> from which it follows that triangle detection can be solved in time <math>O(m^{1.407})</math>. Another approach is to find the trace of {{math|''A''{{sup|3}}}}, where {{mvar|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 <math>O(n^{\omega})</math>, where <math>n</math> is the number of vertices.

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

As {{Harvtxt|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 {{math|Θ(''n''{{sup|2}})}}. However, for quantum algorithms, the best known lower bound is {{math|Ω(''n'')}}, but the best known algorithm is {{math|''O''(''n''{{sup|5/4}})}}.<ref>{{harvtxt|Le Gall|2014}}, improving previous algorithms by {{harvtxt|Lee|Magniez|Santha|2013}} and {{harvtxt|Belovs|2012}}.</ref>

==Independence number and Ramsey theory== An independent set of <math>\lfloor\sqrt{n}\rfloor</math> vertices (where <math>\lfloor\cdot\rfloor</math> is the floor function) in an ''n''-vertex triangle-free graph is easy to find: either there is a vertex with at least <math>\lfloor\sqrt{n}\rfloor</math> neighbors (in which case those neighbors are an independent set) or all vertices have strictly less than <math>\lfloor\sqrt{n}\rfloor</math> neighbors (in which case any maximal independent set must have at least <math>\lfloor\sqrt{n}\rfloor</math> vertices).<ref>{{harvtxt|Boppana|Halldórsson|1992}} p. 184, based on an idea from an earlier coloring approximation algorithm of Avi Wigderson.</ref> This bound can be tightened slightly: in every triangle-free graph there exists an independent set of <math>\Omega(\sqrt{n\log n})</math> vertices, and in some triangle-free graphs every independent set has <math>O(\sqrt{n\log n})</math> vertices.{{sfnp|Kim|1995}} One way to generate triangle-free graphs in which all independent sets are small is the ''triangle-free process''<ref>{{harvtxt|Erdős|Suen|Winkler|1995}}; {{harvtxt|Bohman|2009}}.</ref> 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 <math>O(\sqrt{n\log n})</math>. It is also possible to find regular graphs with the same properties.{{sfnp|Alon|Ben-Shimon|Krivelevich|2010}}

These results may also be interpreted as giving asymptotic bounds on the Ramsey numbers R(3,''t'') of the form <math>\Theta(\tfrac{t^2}{\log t})</math>: if the edges of a complete graph on <math>\Omega(\tfrac{t^2}{\log t})</math> 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== [[File:Groetzsch graph 4COL.svg|thumb|upright=1.35|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.<ref>{{Harvtxt|Grötzsch|1959}}; {{Harvtxt|Thomassen|1994}}).</ref> 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<ref>{{harvtxt|Descartes|1947}}; {{harvtxt|Descartes|1954}}</ref>). This construction started from the graph with a single vertex say <math>G_1</math> and inductively constructed <math>G_{k+1}</math> from <math>G_{k}</math> as follows: let <math>G_{k}</math> have <math>n</math> vertices, then take a set <math>Y</math> of <math>k(n-1)+1</math> vertices and for each subset <math>X</math> of <math>Y</math> of size <math>n</math> add a disjoint copy of <math>G_{k}</math> and join it to <math>X</math> with a matching. From the pigeonhole principle it follows inductively that <math>G_{k+1}</math> is not <math>k</math> colourable, since at least one of the sets <math>X</math> must be coloured monochromatically if we are only allowed to use k colours. {{harvtxt|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''&nbsp;+&nbsp;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.{{sfnp|Chvátal|1974}} {{harvtxt|Gimbel|Thomassen|2000}} and {{harvtxt|Nilli|2000}} showed that the number of colors needed to color any ''m''-edge triangle-free graph is :<math>O \left(\frac{m^{1/3}}{(\log m)^{2/3}} \right)</math> 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. {{harvtxt|Andrásfai|Erdős|Sós|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, {{Harvtxt|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, {{Harvtxt|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. {{Harvtxt|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, because Häggkvist's graph requires four colors and has exactly 10''n''/29 neighbors per vertex. Finally, {{Harvtxt|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<ref>see {{Harvtxt|Erdős|Simonovits|1973}}.</ref> found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3&nbsp;&minus;&nbsp;ε)''n'' for any ε&nbsp;>&nbsp;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 <math>KG_{3k-1, k}</math> is triangle free and has chromatic number <math>k + 1</math> *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=== {{reflist|30em}}

===Sources=== {{refbegin|30em}} *{{citation | last1 = Abboud | first1 = Amir | last2 = Bringmann | first2 = Karl | last3 = Khoury | first3 = Seri | last4 = Zamir | first4 = Or | editor1-last = Leonardi | editor1-first = Stefano | editor2-last = Gupta | editor2-first = Anupam | arxiv = 2204.10465 | contribution = Hardness of approximation in P via short cycle removal: cycle detection, distance oracles, and beyond | doi = 10.1145/3519935.3520066 | pages = 1487–1500 | publisher = {ACM} | title = STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 | year = 2022| isbn = 978-1-4503-9264-8 | s2cid = 248366492 }} *{{citation | title = A note on regular Ramsey graphs | year = 2010| last1 = Alon | last2 = Ben-Shimon | last3 = Krivelevich | first1 = Noga | first2 = Sonny | first3 = Michael | author1-link = Noga Alon | authorlink3 = Michael Krivelevich | journal = Journal of Graph Theory | volume = 64 | issue = 3 | pages = 244–249 | arxiv = 0812.2386 | doi = 10.1002/jgt.20453 | mr = 2674496 | s2cid = 1784886}}. *{{citation | title = Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands | year = 1994| last1 = Alon | last2 = Yuster | last3 = Zwick | first1 = N. | first2 = R. | author2-link = Raphael Yuster | first3 = U. | author1-link = Noga Alon | author3-link = Uri Zwick | pages = 354–364 | contribution = Finding and counting given length cycles | title-link = European Symposium on Algorithms}}. *{{citation | title = On the connection between chromatic number, maximal clique and minimal degree of a graph | year = 1974| last1 = Andrásfai | last2 = Erdős | last3 = Sós | first1 = B. | first2 = P. | first3 = V. T. | author2-link = Paul Erdős | author3-link = Vera Sós | journal = Discrete Mathematics | volume = 8 | issue = 3 | pages = 205–218 | doi = 10.1016/0012-365X(74)90133-2 | url = http://real.mtak.hu/110445/1/1974-18.pdf}}. *{{citation | last = Belovs | first = Aleksandrs | title = Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12) | year = 2012| pages = 77–84 | contribution = Span programs for functions with constant-sized 1-certificates | location = New York, NY, USA | publisher = ACM | doi = 10.1145/2213977.2213985 | isbn = 978-1-4503-1245-5 | arxiv = 1105.4024 | s2cid = 18771464 }}. *{{citation | last = Bohman | first = Tom | title = The triangle-free process | year = 2009| journal = Advances in Mathematics | volume = 221 | issue = 5 | pages = 1653–1677 | arxiv = 0806.4375 | doi = 10.1016/j.aim.2009.02.018 | doi-access=free | mr = 2522430 | s2cid = 17701040 }}. *{{citation | title = Approximating maximum independent sets by excluding subgraphs | year = 1992| last1 = Boppana | last2 = Halldórsson | first1 = Ravi | first2 = Magnús M. | journal = BIT | volume = 32 | issue = 2 | pages = 180–196 | doi = 10.1007/BF01994876 | mr = 1172185 | s2cid = 123335474}}. *{{citation | title = Dense triangle-free graphs are four-colorable: a solution to the Erdős–Simonovits problem | url = http://perso.ens-lyon.fr/stephan.thomasse/liste/vega11.pdf| year = 2006 | last1 = Brandt | last2 = Thomassé | first1 = S. | first2 = S. }}. *{{citation | last = Chan | first = Timothy M. | editor1-last = Bansal | editor1-first = Nikhil | editor2-last = Nagarajan | editor2-first = Viswanath | arxiv = 2211.05345 | contribution = Finding triangles and other small subgraphs in geometric intersection graphs | doi = 10.1137/1.9781611977554.ch68 | pages = 1777–1805 | publisher = {SIAM} | title = Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 | year = 2023 | isbn = 978-1-61197-755-4 }} *{{citation | title = Arboricity and subgraph listing algorithms | year = 1985| last1 = Chiba | last2 = Nishizeki | first1 = N. | first2 = T. | author2-link = Takao Nishizeki | journal = SIAM Journal on Computing | volume = 14 | issue = 1 | pages = 210–223 | doi = 10.1137/0214017 | s2cid = 207051803}}. *{{citation | last = Descartes | first = Blanche | title = A three colour problem | date = April 1947 | authorlink = Blanche Descartes | journal = Eureka | volume = 21}}. *{{citation | last = Descartes | first = Blanche | title = Solution to Advanced Problem no. 4526 | year = 1954 | author-link = Blanche Descartes | journal = Amer. Math. Monthly | volume = 61 | pages = 352}}. *{{citation | last = Chvátal | first = Vašek | title = Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973) | year = 1974| author-link = Václav Chvátal | series = Lecture Notes in Mathematics | volume = 406 | pages = 243–246 | contribution = The minimality of the Mycielski graph | publisher = Springer-Verlag }}. *{{citation | title = On a valence problem in extremal graph theory | year = 1973| last1 = Erdős | last2 = Simonovits | first1 = P. | first2 = M. | author1-link = Paul Erdős | author2-link = Miklós Simonovits | journal = Discrete Mathematics | volume = 5 | issue = 4 | pages = 323–334 | doi = 10.1016/0012-365X(73)90126-X | doi-access = free }}. *{{citation | title = On the size of a random maximal graph | year = 1995| last1 = Erdős | last2 = Suen | last3 = Winkler | first1 = P. | first2 = S. | first3 = P. | author1-link = Paul Erdős | author3-link = Peter Winkler | journal = Random Structures and Algorithms | volume = 6 | issue = 2–3 | pages = 309–318 | doi = 10.1002/rsa.3240060217 }}. *{{citation | title = Coloring triangle-free graphs with fixed size | year = 2000| last1 = Gimbel | last2 = Thomassen | first1 = John | first2 = Carsten | author2-link = Carsten Thomassen (mathematician) | journal =Discrete Mathematics | volume = 219 | issue = 1–3 | pages = 275–277 | doi = 10.1016/S0012-365X(00)00087-X | doi-access = free }}. *{{citation | last = Grötzsch | first = H. | title = Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel | year = 1959| authorlink = Herbert Grötzsch | journal = Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe | volume = 8 | pages = 109–120 }}. *{{citation | last = Häggkvist | first = R. | title = Graph Theory (Cambridge, 1981) | series = North-Holland Mathematics Studies | volume = 62 | year = 1981| pages = 89–99 | contribution = Odd cycles of specified length in nonbipartite graphs | url=https://www.sciencedirect.com/science/article/pii/S0304020808735527 | doi = 10.1016/S0304-0208(08)73552-7 | isbn = 978-0-444-86449-9 | url-access = subscription }}. *{{citation | title = Median graphs and triangle-free graphs | year = 1999| last1 = Imrich | last2 = Klavžar | last3 = Mulder | first1 = Wilfried | first2 = Sandi | first3 = Henry Martyn | journal = SIAM Journal on Discrete Mathematics | volume = 12 | issue = 1 | pages = 111–118 | doi = 10.1137/S0895480197323494 | mr = 1666073 | s2cid = 14364050}}. *{{citation | title = Finding a minimum circuit in a graph | year = 1978| last1 = Itai | last2 = Rodeh | first1 = A. | first2 = M. | journal = SIAM Journal on Computing | volume = 7 | issue = 4 | pages = 413–423 | doi = 10.1137/0207033 }}. *{{citation | last1 = Jin | first1 = Ce | last2 = Xu | first2 = Yinzhan | editor1-last = Saha | editor1-first = Barna | editor2-last = Servedio | editor2-first = Rocco A. | arxiv = 2211.07048 | contribution = Removing additive structure in 3SUM-based reductions | doi = 10.1145/3564246.3585157 | pages = 405–418 | publisher = {ACM} | title = Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 | year = 2023| isbn = 978-1-4503-9913-5 | s2cid = 253510334 }} *{{citation | last = Jin | first = G. | title = Triangle-free four-chromatic graphs | year = 1995| journal = Discrete Mathematics | volume = 145 | issue = 1–3 | pages = 151–170 | doi = 10.1016/0012-365X(94)00063-O | doi-access = }}. *{{citation | last = Kim | first = J. H. | title = The Ramsey number <math>R(3,t)</math> has order of magnitude <math>\tfrac{t^2}{\log t}</math> | year = 1995 | journal = Random Structures and Algorithms | volume = 7 | issue = 3 | pages = 173–207 | edition = | doi=10.1002/rsa.3240070302| s2cid = 16658980 }}. *{{citation | last = Le Gall | first = François | contribution = Improved quantum algorithm for triangle finding via combinatorial arguments | date = October 2014 | doi = 10.1109/focs.2014.31 | pages = 216–225 | publisher = IEEE | title = Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014)| arxiv = 1407.0085 | isbn = 978-1-4799-6517-5 | s2cid = 5760574 }}. *{{citation | title= Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013): New Orleans, Louisiana, USA, January 6–8, 2013 | date = 2013| last1 = Lee | last2 = Magniez | last3 = Santha | first1 = Troy | first2 = Frédéric | first3 = Miklos | pages = 1486–1502 | contribution = Improved quantum query algorithms for triangle finding and associativity testing | contribution-url = http://dl.acm.org/citation.cfm?id=2627817.2627924 |contribution-url-access = subscription |publisher=Association for Computing Machinery (ACM); Society for Industrial and Applied Mathematics (SIAM) | isbn = 978-1-611972-51-1 }}. *{{citation | last = Mycielski | first = J. | title = Sur le coloriage des graphes | year = 1955| authorlink = Jan Mycielski | journal = Colloq. Math. | volume = 3 | issue = 2 | pages = 161–162 | doi = 10.4064/cm-3-2-161-162 | doi-access = free}}. *{{citation | last = Nilli | first = A. | authorlink = Noga Alon | title = Triangle-free graphs with large chromatic numbers | year = 2000| journal = Discrete Mathematics | volume = 211 | issue = 1–3 | pages = 261–262 | doi = 10.1016/S0012-365X(99)00109-0 | doi-access = free }}. *{{citation | last = Shearer | first = J. B. | title = Note on the independence number of triangle-free graphs | year = 1983| journal = Discrete Mathematics | volume = 46 | issue = 1 | pages = 83–87 | doi = 10.1016/0012-365X(83)90273-X | doi-access = free }}. *{{citation | last = Thomassen | first = C. | title = Grötzsch's 3-color theorem | year = 1994| authorlink = Carsten Thomassen (mathematician) | journal = Journal of Combinatorial Theory, Series B | volume = 62 | issue = 2 | pages = 268–279 | doi = 10.1006/jctb.1994.1069 | doi-access = free }}. {{refend}}

== External links ==

* {{Citation | url=http://www.graphclasses.org/classes/gc_371.html | title=Graphclass: triangle-free | work =Information System on Graph Classes and their Inclusions}}

Category:Graph families