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.
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
\tildeOl(m2\omega/(\omega+1)r)
\tildeO
\omega
\omega<2.372
O(m1.407)
O(n\omega)
n
Even if matrix multiplication algorithms with time
O(n2)
O(m4/3)
O(n2)
O(m4/3-\delta)
\delta>0
O(n\omega-\delta)
As 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 . However, for quantum algorithms, the best known lower bound is, but the best known algorithm is .[2]
An independent set of
\lfloor\sqrt{n}\rfloor
\lfloor ⋅ \rfloor
\lfloor\sqrt{n}\rfloor
\lfloor\sqrt{n}\rfloor
\lfloor\sqrt{n}\rfloor
\Omega(\sqrt{nlogn})
O(\sqrt{nlogn})
O(\sqrt{nlogn})
These results may also be interpreted as giving asymptotic bounds on the Ramsey numbers R(3,t) of the form
\Theta(\tfrac{t2}{logt})
\Omega(\tfrac{t2}{logt})
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.[5] 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). This construction started from the graph with a single vertex say
G1
Gk+1
Gk
Gk
n
Y
k(n-1)+1
X
Y
n
Gk
X
Gk+1
k
X
O\left(
m1/3 | |
(logm)2/3 |
\right)
There have also been several results relating coloring to minimum degree in triangle-free graphs. 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, 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, 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. 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, 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[6] found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 - ε)n for any ε > 0.
KG3k-1,
k+1