A note on a conjecture of Gallai (Q1805373)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on a conjecture of Gallai |
scientific article |
Statements
A note on a conjecture of Gallai (English)
0 references
8 October 1995
0 references
A graph \(G\) is said to be wheel-free if it has the property that for every vertex \(x\) of \(G\), the neighbourhood \(\Gamma(x)\) of \(x\) induces an acyclic subgraph in \(G\). A conjecture of Gallai states that the number of triangles in a wheel-free graph with \(n\) vertices is at most \(n^ 2/8\). Here it is shown that this number is at most \((1+ o(1))n^ 2/7\). Many non-isomorphic examples of wheel-free graphs which do contain the conjectured maximum number of triangles are also constructed. This conjecture has recently been shown to be false by Z. Füredi, M. Goemans and D. Kleitman, who gave an example of a wheel-free graph with \(n\) vertices that contains \(n^ 2/7.5\) triangles.
0 references
conjecture of Gallai
0 references
triangles
0 references
wheel-free graph
0 references