Bounding Width on Graph Classes of Constant Diameter

Abstract

We determine if the width of a graph class $\mathcal{G}$ changes from unbounded to bounded if we consider only those graphs from $\mathcal{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,\dots \}$ and partial classifications for $d=2$ and $d=3$.