Bounded treedepth for even-cycle-subgraph-free graphs of diameter three

Let r4r\geq 4. A graph is C2rC_{2r}-subgraph-free if it contains no subgraph isomorphic to the cycle C2rC_{2r}. The diameter of a graph is the maximum distance between two vertices. The even-cycle treedepth conjecture. For every r4r\geq 4, the class of C2rC_{2r}-subgraph-free graphs of diameter at most 33 has bounded treedepth.

The conjecture would complete the classification of bounded treedepth for even-cycle-subgraph-free graphs of diameter three. Boundedness is established for r=4r=4 by an involved case analysis and for r{5,,12}r\in\{5,\ldots,12\} with computer assistance, while the general case remains open.

Sources & referencesView supporting material

Primary source

Konrad K. Dabrowski, Tala Eagling-Vose, Noleen Köhler, Sebastian Ordyniak and Daniël Paulusma, “Bounding Width on Graph Classes of Constant Diameter”, arXiv:2505.19926 (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.