Triangle-covering conjecture for graphs above the Mantel threshold
Triangle-covering conjecture for graphs above the Mantel threshold
Let be an -vertex graph, let denote its number of triangles, and let be the minimum size of a vertex set meeting every triangle. For integers and sufficiently large , consider the graph obtained from the complete bipartite graph by adding pairwise disjoint edges in the first part and one edge in the second part, then deleting edges incident with one endpoint of that second-part edge. Triangle-covering conjecture. If has vertices and edges, satisfies , and is large, then contains at least as many triangles as , namely
The construction shows the proposed bound is attainable for sufficiently large ; the lower-bound assertion itself is left as a conjecture.
Sources & referencesView supporting material
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.