Bounding Width on Graph Classes of Constant Diameter
摘要
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,\ldots \}\) and partial classifications for \(d=2\) and \(d=3\) .