Bounded treedepth for even-cycle-subgraph-free graphs of diameter three
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.