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, or locally independent graphs. Every bipartite graph is triangle-free, but triangle-free graphs may have arbitrarily large chromatic number (Mycielski 1955).
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.
It is possible to test whether a graph with m edges is triangle-free in time O(m3/2) (Itai and Rodeh 1978; Chiba and Nishizeki 1985).
References
- Chiba, N.; Nishizeki, T. (1985). "Arboricity and subgraph listing algorithms". SIAM J. Comput. 14: 210–223.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Itai, A.; Rodeh, M. (1978). "Finding a minimum circuit in a graph". SIAM J. Comput. 7: 413–423.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Mycielski, J. (1955). "Sur le coloriage des graphes". Colloq. Math. 3: 161–162.
- Shearer, J. B. (1983). "Note on the independence number of triangle-free graphs". Discrete Mathematics. 46 (1): 83–87.