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 ${\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 and ${\displaystyle \omega }$ is the exponent of fast matrix multiplication.[1] As of 2023 it is known that ${\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^{2-\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]

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.

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.

• 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

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