triangle-free graph

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 $m$ edges is triangle-free in time $\backslash tilde\; O\backslash bigl(m^\{2\backslash omega/(\backslash omega+1)\}\backslash bigr)$ where the $\backslash tilde\; O$ hides sub-polynomial factors. Here $\backslash omega$ is the exponent of fast matrix multiplication;{{sfnp|Alon|Yuster|Zwick|1994}} from which it follows that triangle detection can be solved in time $O(m^\{1.407\})$. 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 $O(n^\{\backslash omega\})$, where $n$ is the number of vertices.

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

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}})}}.{{harvtxt|Le Gall|2014}}, improving previous algorithms by {{harvtxt|Lee|Magniez|Santha|2013}} and {{harvtxt|Belovs|2012}}.

An independent set of $\backslash lfloor\backslash sqrt\{n\}\backslash rfloor$ vertices (where $\backslash lfloor\backslash cdot\backslash rfloor$ is the floor function) in an n-vertex triangle-free graph is easy to find: either there is a vertex with at least $\backslash lfloor\backslash sqrt\{n\}\backslash rfloor$ neighbors (in which case those neighbors are an independent set) or all vertices have strictly less than $\backslash lfloor\backslash sqrt\{n\}\backslash rfloor$ neighbors (in which case any maximal independent set must have at least $\backslash lfloor\backslash sqrt\{n\}\backslash rfloor$ vertices).{{harvtxt|Boppana|Halldórsson|1992}} p. 184, based on an idea from an earlier coloring approximation algorithm of Avi Wigderson. This bound can be tightened slightly: in every triangle-free graph there exists an independent set of $\backslash Omega(\backslash sqrt\{n\backslash log\; n\})$ vertices, and in some triangle-free graphs every independent set has $O(\backslash sqrt\{n\backslash log\; n\})$ vertices.{{sfnp|Kim|1995}} One way to generate triangle-free graphs in which all independent sets are small is the triangle-free process{{harvtxt|Erdős|Suen|Winkler|1995}}; {{harvtxt|Bohman|2009}}. 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 $O(\backslash sqrt\{n\backslash log\; n\})$. 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 $\backslash Theta(\backslash tfrac\{t^2\}\{\backslash log\; t\})$: if the edges of a complete graph on $\backslash Omega(\backslash tfrac\{t^2\}\{\backslash 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.

File:Groetzsch graph 4COL.svg 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.{{Harvtxt|Grötzsch|1959}}; {{Harvtxt|Thomassen|1994}}). 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{{harvtxt|Descartes|1947}}; {{harvtxt|Descartes|1954}}). This construction started from the graph with a single vertex say $G\_1$ and inductively constructed $G\_\{k+1\}$ from $G\_\{k\}$ as follows: let $G\_\{k\}$ have $n$ vertices, then take a set $Y$ of $k(n-1)+1$ vertices and for each subset $X$ of $Y$ of size $n$ add a disjoint copy of $G\_\{k\}$ and join it to $X$ with a matching. From the pigeonhole principle it follows inductively that $G\_\{k+1\}$ is not $k$ colourable, since at least one of the sets $X$ 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 + 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

:$O\; \backslash left(\backslash frac\{m^\{1/3\}\}\{(\backslash log\; m)^\{2/3\}\}\; \backslash 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. {{harvtxt|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, {{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 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, {{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 Hajnalsee {{Harvtxt|Erdős|Simonovits|1973}}. found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)n for any ε > 0.

• 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 $KG\_\{3k-1,\; k\}$ is triangle free and has chromatic number $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

{{reflist|30em}}

{{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| 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}}

• {{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 = Vasek Chvatal

| 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)

| 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

}}.

• {{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| 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 $R(3,t)$ has order of magnitude $\backslash tfrac\{t^2\}\{\backslash log\; t\}$

| 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}}

• {{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