Sparse triangle-free diameter-two graph conjecture

About 1 year old · traced to

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 t⩾2t\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 n⩾n0n\geqslant n_0 vertices, then GG is the star graph K1,n−1K_{1,n-1}. 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

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.