Bounding Width on Graph Classes of Constant Diameter

May 26, 2025 ยท The Ethereal ยท ๐Ÿ› International Workshop on Graph-Theoretic Concepts in Computer Science

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Konrad K. Dabrowski, Tala Eagling-Vose, Noleen Kรถhler, Sebastian Ordyniak, Daniรซl Paulusma arXiv ID 2505.19926 Category cs.DM: Discrete Mathematics Cross-listed cs.DS, math.CO Citations 0 Venue International Workshop on Graph-Theoretic Concepts in Computer Science Last Checked 5 months ago
Abstract
We determine if the width of a graph class ${\cal G}$ changes from unbounded to bounded if we consider only those graphs from ${\cal G}$ whose diameter is bounded. As parameters we consider treedepth, pathwidth, treewidth and clique-width, and as graph classes we consider classes defined by forbidding some specific graph $F$ as a minor, induced subgraph or subgraph, respectively. Our main focus is on treedepth for $F$-subgraph-free graphs of diameter at most~$d$ for some fixed integer $d$. We give classifications of boundedness of treedepth for $d\in \{4,5,\ldots\}$ and partial classifications for $d=2$ and $d=3$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Discrete Mathematics