Tyomkyn–Uzzell's balanced double-broom conjecture for triangle-free distance graphs

Let GG be an nn-vertex graph, and let GkG_k be its graph of pairs at distance exactly kk. Write DkD_k for the kk-distance graph of a graph DD, and call DD a balanced double broom when it is the double broom specified in the conjecture.

Tyomkyn–Uzzell's conjecture. For k3k\geq 3 and nk+1n\geq k+1, except when k=3k=3 and n=8n=8, every nn-vertex graph GG such that GkG_k is triangle-free satisfies

E(Gk)(nk+1)24.|E(G_k)|\leq\frac{(n-k+1)^2}{4}.

Moreover, if equality holds, then GkG_k is isomorphic to DkD_k, where DD is a balanced double broom.

This conjecture strengthens the previously known result for sufficiently large kk and sufficiently large nn as a function of kk, extending it to all indicated values of kk and nn. The source says that it would imply the corresponding conclusion for k=3k=3 and n9n\geq 9; no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Zhen He, Nika Salia, Casey Tompkins and Xiutao Zhu, “Turán-Type Extremal Results for Distance-k Graphs”, arXiv:2604.28060 (2026).

Additional references

2 papers in this index state this conjecture (2013–2026). The statement above is taken from the most recent of them; the others are arXiv:1312.1013.

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.