Bounded treedepth for even-cycle-subgraph-free graphs of diameter three
Let . A graph is -subgraph-free if it contains no subgraph isomorphic to the cycle . The diameter of a graph is the maximum distance between two vertices. The even-cycle treedepth conjecture. For every , the class of -subgraph-free graphs of diameter at most 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 by an involved case analysis and for with computer assistance, while the general case remains open.
References
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
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.