A note on a conjecture of Gallai (Q1805373): Difference between revisions

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.