Triangle-free graph

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.

Another approach is to find the trace of A3, where A is the adjacency matrix of the graph.

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

were discovered, the best time bounds that could be hoped for from these approaches are

In fine-grained complexity, the sparse triangle hypothesis is an unproven computational hardness assumption asserting that no time bound of the form

It, and the corresponding dense triangle hypothesis that no time bound of the form

[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 Θ(n2).

is the floor function) in an n-vertex triangle-free graph is easy to find: either there is a vertex with at least

neighbors (in which case any maximal independent set must have at least

[4] 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

[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

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

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.

[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

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.

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