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

It has long been known that the following basic objects are obstructions to bounded treewidth: for arbitrarily large t, (1) the complete graph K t , (2) the complete bipartite graph K t,t , (3) a subdivision of the (t × t)-wall and (4) the line graph of a subdivision of the (t × 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 treewidth 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.