Triangle-covering conjecture for graphs above the Mantel threshold

About 6 years old · traced to

Let GG be an nn-vertex graph, let T(G)T(G) denote its number of triangles, and let τ△(G)\tau_{\triangle}(G) be the minimum size of a vertex set meeting every triangle. For integers 0<t<s0<t<s and sufficiently large nn, consider the graph K⌈n/2⌉,⌊n/2⌋s,tK_{\lceil n/2\rceil,\lfloor n/2\rfloor}^{s,t} obtained from the complete bipartite graph by adding s−1s-1 pairwise disjoint edges in the first part and one edge in the second part, then deleting s−ts-t edges incident with one endpoint of that second-part edge. Triangle-covering conjecture. If GG has nn vertices and ⌊n24⌋+t\left\lfloor\frac{n^2}{4}\right\rfloor+t edges, satisfies τ△(G)≥s\tau_{\triangle}(G)\geq s, and n≥n(t,s)n\geq n(t,s) is large, then GG contains at least as many triangles as K⌈n/2⌉,⌊n/2⌋s,tK_{\lceil n/2\rceil,\lfloor n/2\rfloor}^{s,t}, namely

(s−1)⌊n2⌋+⌈n2⌉−2(s−t).(s-1)\left\lfloor\frac n2\right\rfloor+\left\lceil\frac n2\right\rceil-2(s-t).

The construction shows the proposed bound is attainable for sufficiently large nn; the lower-bound assertion itself is left as a conjecture.

References

Primary source

Chuanqi Xiao and Gyula O. H. Katona, “The number of triangles is more when they have no common vertex”, arXiv:2003.04450 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.