Cubic-cage order conjecture

About 1 year old · traced to

A cubic graph is a graph in which every vertex has degree 33. The girth of a graph is denoted by girth⁡(G)\operatorname{girth}(G), its order by ∣V(G)∣|V(G)|, and cc denotes a constant.

Cubic-cage conjecture. For infinitely many integers gg, there exists a cubic graph GG such that

girth⁡(G)≥gand∣V(G)∣≤c2g/2.\operatorname{girth}(G)\geq g\qquad\text{and}\qquad |V(G)|\leq c2^{g/2}.

This is proposed as a strengthening of the available general upper bound for the order of cubic cages. It would support the polynomial-expansion path-degeneracy conjecture and further lower-bound conjectures in the paper.

References

Primary source

Y. Lin and P. Ossona de Mendez, “Path degeneracy and applications”, arXiv:2503.18614 (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.