๐ฎ
๐ฎ
The Ethereal
Bounding Width on Graph Classes of Constant Diameter
May 26, 2025 ยท The Ethereal ยท ๐ International Workshop on Graph-Theoretic Concepts in Computer Science
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Discrete Mathematics
๐ฎ
๐ฎ
The Ethereal
An Introduction to Temporal Graphs: An Algorithmic Perspective
๐ฎ
๐ฎ
The Ethereal
Guarantees for Greedy Maximization of Non-submodular Functions with Applications
๐ฎ
๐ฎ
The Ethereal
A note on the triangle inequality for the Jaccard distance
๐ฎ
๐ฎ
The Ethereal
Fast clique minor generation in Chimera qubit connectivity graphs
๐ฎ
๐ฎ
The Ethereal