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\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bounding Width on Graph Classes of Constant Diameter

  • Konrad K. Dabrowski,
  • Tala Eagling-Vose,
  • Noleen Köhler,
  • Sebastian Ordyniak,
  • Daniël Paulusma

摘要

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\) .