Bounding Width on Graph Classes of Constant Diameter

2025/05/26 by Konrad K. Dabrowski, Dabrowski, Konrad K., Tala Eagling-Vose +7
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2505.19926

openalex publication_date 2025/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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∈ \4,5,…\ and partial classifications for d=2 and d=3.

Citations

• 3-Coloring C₄ or C₃-free Diameter Two Graphs
• Induced subgraphs and path decompositions
• Faster 3-coloring of small-diameter graphs
• Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
• Tree-width dichotomy
• On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
• The Complexity Landscape of Decompositional Parameters for ILP
• Improved Bounds for the Flat Wall Theorem
• Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs

Related

• Comparing Width Parameters on Graph Classes
• Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• Between Treewidth and Clique-width
• Directed branch-width: A directed analogue of tree-width
• Tree-width dichotomy