Countable Graphs with Finite Path-width: Characterisation and Universality
Discrete Mathematics
Summary
The authors examine two ways to measure how 'tree-like' infinite graphs are, called path-width and line-width. They describe which infinite graphs have a finite path-width by identifying certain forbidden features. They also explore whether a single big graph can contain all graphs with bounded path-width or line-width as subgraphs. They find a universal graph for graphs with bounded line-width but show no such universal graph exists for locally finite graphs with path-width 1. Finally, they prove that any universal graph for graphs with path-width up to k must have line-width larger than k.
Authors
Tony Huynh, Freddie Illingworth, Nikolai Karol, Florian Lehner, Chun-Hung Liu, János Pach, David R. Wood
Abstract
We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs that do not have infinitely many vertices of infinite degree, do not have infinitely many pairwise disjoint infinite paths, and contain no subdivision of some finite tree of maximum degree 3. We then investigate universality under the subgraph relation for graphs of bounded path-width or line-width. In particular, we prove that there exists a universal graph with line-width $\mathcal{O}(k^2)$ for the class of graphs with line-width at most $k$. In contrast, we show that no graph of finite path-width is universal for the class of locally finite graphs with path-width $1$. Finally, we show that for each $k\geq 2$, every universal graph for the class of graphs with path-width at most $k$ has line-width at least $k + 1$.