t-sails and sparse hereditary classes of unbounded tree-width

DOI10.1016/J.EJC.2024.104005MaRDI QIDQ6425966zbMATH OpenFDO

Authors Daniel G. Cocks

Publication date 9 February 2023

Full work available at URL https://doi.org/10.1016/J.EJC.2024.104005

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: It has long been known that the following basic objects are obstructions to bounded tree-width: for arbitrarily large $t$, $(1)$ a subdivision of the complete graph $K_t$, $(2)$ a subdivision of the complete bipartite graph $K_{t,t}$, $(3)$ a subdivision of the $(timest)$-wall and $(4)$ a line graph of a subdivision of the $(timest)$-wall. We are now able to add a further emph{boundary object} to this list, a subdivision of a emph{$t$-sail}. We identify hereditary graph classes of unbounded tree-width that do not contain any of the four basic obstructions but instead contain arbitrarily large $t$-sails or subdivisions of a $t$-sail. We also show that these sparse graph classes do not contain a minimal class of unbounded tree-width. These results have been obtained by studying emph{path-star} graph classes, a type of sparse hereditary graph class formed by combining a path (or union of paths) with a forest of stars, characterised by an infinite word over a possibly infinite alphabet.

This page was built for publication: $t$-sails and sparse hereditary classes of unbounded tree-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6425966)