Sparse triangle-free diameter-two graph conjecture

Let GG be a finite simple graph. A graph is triangle-free if it contains no triangle, and has diameter 22 if every two vertices are at distance at most 22. Sparse triangle-free diameter-two graph conjecture. For every integer t2t\geqslant2, there exists an integer n0n_0 such that if GG is a triangle-free diameter-22 graph that does not contain K2,tK_{2,t} as a subgraph and has nn0n\geqslant n_0 vertices, then GG is the star graph K1,n1K_{1,n-1}. 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

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.