Sparse triangle-free diameter-two graph conjecture
Let be a finite simple graph. A graph is triangle-free if it contains no triangle, and has diameter if every two vertices are at distance at most . Sparse triangle-free diameter-two graph conjecture. For every integer , there exists an integer such that if is a triangle-free diameter- graph that does not contain as a subgraph and has vertices, then is the star graph . The conjecture is attributed in the paper to Wood and is presented as an open problem.
References
Primary source
Jofre Costa, Eric Luu, David R. Wood and Jung Hon Yip, “Verifying Hadwiger's Conjecture for Examples of Graphs with α(G) = 2”, arXiv:2512.17114 (2025).
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
No solutions have been posted yet.