Cambie–Cames van Batenburg–Joannis de Verclos–Kang conjecture for h3(Δ)h_3(\Delta)

For positive integers Δ\Delta and tt, let ht(Δ)h_t(\Delta) be the smallest integer such that every graph GG with at least ht(Δ)h_t(\Delta) edges and maximum degree Δ(G)≤Δ\Delta(G)\le \Delta contains two edges at distance at least tt. Cambie–Cames van Batenburg–Joannis de Verclos–Kang conjecture.

h3(Δ)≤Δ3−Δ2+Δ+2.h_3(\Delta)\le \Delta^3-\Delta^2+\Delta+2.

This concerns the next case of the edge degree-diameter problem after the solved t=2t=2 case. The paper states it as an open conjecture and notes that blow-ups of C5C_5 provide tight examples for the preceding case.

References

Primary source

Hitesh Kumar, Bojan Mohar and Shivaramakrishna Pragada, “An improved bound for the strong clique index of graphs”, arXiv:2607.02698 (2026).

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.