What type of study is this?

This is a Quantitative Study study.

September 30, 2025Open Access

Bounding Width on Graph Classes of Constant Diameter

Key Points

The study classifies the change of treedepth from unbounded to bounded in graphs with bounded diameter.
It specifically focuses on graphs defined by forbidding certain graphs as minors or subgraphs.
Classifications of treedepth are provided for diameters up to 5, with partial classifications for 2 and 3.
The findings imply important structural distinctions for various graph classes based on minor and induced subgraph constraints.

Abstract

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

Bounding Width on Graph Classes of Constant Diameter

Key Points

Abstract

Cite This Study

Also Consider

Also Consider