What type of study is this?

This is a Quantitative Study study.

September 30, 2025Open Access

Bounding Width on Graph Classes of Constant Diameter

Puntos clave

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.

Resumen

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.

Leer artículo completoexternamente

Me gusta

Guardar

Ver artículo completo

Cite This Study

Dabrowski et al. (Mon,) studied this question.

synapsesocial.com/papers/68dc12c58a7d58c25ebb0974 https://doi.org/https://doi.org/10.48550/arxiv.2505.19926

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Me gusta

Guardar

Ver artículo completo