Sparse triangle-free diameter-two graph conjecture
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.