# 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.

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 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 O(*m*^{1.41}).Template:Sfnp Another approach is to find the trace of *A*^{3}, 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 relies on matrix multiplication, since it gets the time complexity down to O(*n*^{2.373}), where *n* is the number of vertices.

As Template:Harvtxt show, 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*^{2}). However, for quantum algorithms, the best known lower bound is Ω(*n*), but the best known algorithm is O(*n*^{1.29}) due to Template:Harvtxt.

## Independence number and Ramsey theory

An independent set of √*n* vertices in an *n*-vertex triangle-free graph is easy to find: either there is a vertex with greater than √*n* neighbors (in which case those neighbors are an independent set) or all vertices have fewer than √*n* neighbors (in which case any maximal independent set must have at least √*n* vertices).^{[1]} 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 vertices.Template:Sfnp One way to generate triangle-free graphs in which all independent sets are small is the *triangle-free process*^{[2]} 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.Template:Sfnp

These results may also be interpreted as giving asymptotic bounds on the Ramsey numbers R(3,*t*) of the form : if the edges of a complete graph on 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

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

Template:Harvtxt 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.Template:Sfnp Template:Harvtxt and Template:Harvtxt 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. Template:Harvtxt 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, Template:Harvtxt 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, Template:Harvtxt 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. Template:Harvtxt 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, Template:Harvtxt 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^{[4]} found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)*n* for any ε > 0.

## See also

- Monochromatic triangle problem, the problem of partitioning the edges of a given graph into two triangle-free graphs

## References

- Notes

- ↑ Template:Harvtxt p. 184, based on an idea from an earlier coloring approximation algorithm of Avi Wigderson.
- ↑ Template:Harvtxt; Template:Harvtxt
- ↑ Template:Harvtxt; Template:Harvtxt).
- ↑ see Template:Harvtxt.

- Sources

- Template:Cite arxiv.
- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- Template:Cite arxiv.
- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- Template:Cite arxiv.
- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

## External links

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}