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 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 {\displaystyle m} edges is triangle-free in time O ~ ( m 2 ω / ( ω + 1 ) ) {\displaystyle {\tilde {O}}{\bigl (}m^{2\omega /(\omega +1)}{\bigr )}} where the O ~ {\displaystyle {\tilde {O}}} hides sub-polynomial factors. Here ω {\displaystyle \omega } is the exponent of fast matrix multiplication; ω < 2.372 {\displaystyle \omega <2.372} from which it follows that triangle detection can be solved in time O ( m 1.407 ) {\displaystyle O(m^{1.407})} . Another approach is to find the trace of A3, 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 O ( n ω ) {\displaystyle O(n^{\omega })} , where n {\displaystyle n} is the number of vertices. Even if matrix multiplication algorithms with time O ( n 2 ) {\displaystyle O(n^{2})} were discovered, the best time bounds that could be hoped for from these approaches are O ( m 4 / 3 ) {\displaystyle O(m^{4/3})} or O ( n 2 ) {\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 O ( m 4 / 3 − δ ) {\displaystyle O(m^{4/3-\delta })} is possible, for any δ > 0 {\displaystyle \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 ω − δ ) {\displaystyle O(n^{\omega -\delta })} is possible, imply lower bounds for several other computational problems in combinatorial optimization and computational geometry. 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). However, for quantum algorithms, the best known lower bound is Ω(n), but the best known algorithm is O(n5/4).
… excerpt ends here. Continue reading the full article.
