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

Cocks, D. (2024). t-sails and sparse hereditary classes of unbounded tree-width. European Journal of Combinatorics, 122, article no. 104005.

DOI: https://doi.org/10.1016/j.ejc.2024.104005

Abstract

It has long been known that the following basic objects are obstructions to bounded tree-width: for arbitrarily large t, (1) the complete graph K_t, (2) the complete bipartite graph K_t,t, (3) a subdivision of the (t x t)-wall and (4) the line graph of a subdivision of the (t x t)-wall. We now add a further boundary object to this list, a t-sail.
These results have been obtained by studying sparse hereditary path-star graph classes, each of which consists of the finite induced subgraphs of a single infinite graph whose edges can be partitioned into a path (or forest of paths) with a forest of stars, characterised by an infinite word over a possibly infinite alphabet. We show that a path-star class whose infinite graph has an unbounded number of stars, each of which connects an unbounded number of times to the path, has unbounded tree-width. In addition, we show that such a class is not a subclass of the hereditary class of circle graphs.
We identify a collection of nested words with a recursive structure that exhibit interesting characteristics when used to define a path-star graph class. These graph classes do not contain any of the four basic obstructions but instead contain graphs that have large tree-width if and only if they contain arbitrarily large t-sails. We show that these classes are infinitely defined and, like classes of bounded degree or classes excluding a fixed minor, do not contain a minimal class of unbounded tree-width.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI