CS Paper Radar

Countable Graphs with Finite Path-width: Characterisation and Universality

Tony Huynh, Freddie Illingworth, Nikolai Karol, Florian Lehner, Chun-Hung Liu, János Pach, David R. Wood

cs.DM math.CO ·submitted 2026-08-27 22:31 UTC · v1
theory

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$.

Closest papers

Nearest neighbours by meaning across the whole index.

On (Pathwidth, Clique)-boundedness

cs.DM math.CO ·2026-11-17 ·Amir Nikabadi
theory similarity 0.67
Abstract

We prove that every $(\pw,ω)$-bounded class of graphs has bounded tree-independence number, answering a question of Bešter Štorgel, Dallard, Lozin, Milanič, and Zamaraev. We deduce this from a bound on the tree-independence number of graphs with neither $\B_ρ$ nor $K_{σ,σ}$ as an induced minor, where $\B_ρ$ is the complete binary tree of height $ρ$ and the bound depends only on $ρ$ and $σ$. We then obtain an asymptotically sharp bound on the path-independence number of $n$-vertex graphs in any $(\pw,ω)$-bounded class. The lower-bound examples also give counterexamples to a conjecture of Hickingbotham and Joret. We further prove that, for every forest $F$ and every $\ell\in\N$, there is a constant $k=k(F,\ell)\in\N$ such that every graph $G$ with no induced theta or $\ell$-long prism and no induced subgraph isomorphic to $F$ satisfies tree-independence number at most $k$. This proves a strengthened form of a conjecture of Chudnovsky, Hajebi, and Trotignon. Finally, for every integer $s\ge2$, we characterize the forests $F$ for which excluding $F$ as an induced minor and $K_{s,s}$ as an induced subgraph bounds tree-independence number. This extends the characterization of Bonnet, Duhamel, and Hickingbotham, who considered bounded pathwidth with $K_{s,s}$ excluded as a subgraph.

0.09

Asymptotic dimension of graphs excluding an induced or fat minor

cs.DM math.CO ·2026-10-15 ·Robert Hickingbotham, Freddie Illingworth, Piotr Micek, Bartosz Walczak
theory similarity 0.65
Abstract

Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed graph $H$, the class of graphs excluding $H$ as a fat minor has bounded asymptotic dimension. A weaker conjecture asserts the same conclusion for graphs excluding $H$ as an induced minor. We substantially expand the range of graphs $H$ for which these conjectures are known to hold. Specifically, we prove bounded asymptotic dimension for the following classes of graphs: graphs excluding a fixed planar graph as a fat minor; and graphs excluding a fixed string graph as an induced minor. All of our results also hold for the stronger notion of Assouad--Nagata dimension, a refinement of asymptotic dimension. These results have a number of applications, two of which we mention here. First they imply that an induced minor-closed class is $χ$-bounded if and only if it does not contain some Burling graph. Second they imply that, in graph classes excluding a fixed planar graph as an induced minor, treewidth is polynomial in maximum degree.

0.24

Induced packing treewidth III. Branch decompositions

cs.DM math.CO ·2026-11-09 ·Amir Nikabadi, Paweł Rzążewski
theory similarity 0.64
Abstract

The notion of induced packing treewidth aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. In this paper, we introduce induced packing branchwidth, a branch-decomposition analogue of induced packing treewidth. For a graph $H$, the induced $H$-packing branchwidth of a graph $G$, denoted by $\branchpi_H(G)$, is the minimum, over all branch decompositions of $G$, of the largest number of pairwise anticomplete induced copies of $H$ that cross one displayed cut. For $H=P_2$, it equals sim-width. We prove several structural properties of graphs of bounded $\branchpi_H$, for various choices of $H$, including $χ$-boundedness, polynomial degree-boundedness, and metric properties.

0.13

Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers

cs.DM cs.DSmath.CO ·2026-10-21 ·Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung, Ralf Klasing, Lucas Lorieau +1 more
theory similarity 0.64
Abstract · 21 pages, 1 figure

We study how covering a graph by a small number of shortest or approximately shortest paths/walks constrains its treewidth and pathwidth. A path or walk is $(α,β)$-quasi-shortest for $α\geq1$ and $β\geq 0$ if each contiguous segment has length at most $α$ times the distance between its endpoints plus $β$. For graphs vertex-covered by $k$ shortest paths, we establish the first known polynomial pathwidth bound of $O(k^3)$. For edge-coverage, we improve the previously known $O(k^4)$ upper bound to $O(k^2\log k)$. As a main ingredient of the proofs, we first show that if the vertices of a graph can be covered by $k$ $(α,β)$-quasi-shortest paths or walks, then its treewidth is $O_{α,β}(k^2)$; this is a consequence of the fact that such graphs have linear metric growth and the technique developed in [Campbell et al., E-JC 2023]. To obtain the above pathwidth upper bounds, we combine this result with techniques from the literature in a nontrivial way. On the other hand, we show that there exist connected bipartite cubic graph whose edges can be covered by $k$ shortest paths and whose pathwidth is $Ω(k\log k)$, providing the first superlinear lower bound. For graphs covered by $k=2$ $(α,0)$-quasi-shortest paths with $α>1$, we show that, unlike treewidth and unlike the case $α=1$ and $β=0$ of exact shortest paths, the pathwidth may be unbounded. Finally, for every fixed rationals $α\geq1$ and $β\geq 0$, we give XP algorithms with a running time of $n^{f(k,α,β)}$ for some function~$f$ that decide whether the vertices of a graph can be covered by at most $k$ $(α,β)$-quasi-shortest paths or walks. The algorithms combine our treewidth upper bounds with an algorithmic meta-theorem from [Dreier et al., LICS 2025]. [abstract shortened to meet the arXiv requirements]

0.14

Almost Linear Universal Point Sets for Planar Graphs

cs.CG math.CO ·2026-09-10 ·Taylor Gordon
theorycode/data similarity 0.64
Abstract · 12 pages, 2 figures. Lean formalization of the earlier construction: https://github.com/taylorgordon20/math/tree/main/213-superpatterns

A point set is universal for planar graphs on $n$ vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size $n^{1+o(1)}$, improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.

0.37

Small classes have linear neighbourhood complexity

cs.DM math.CO ·2026-11-11 ·John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
theory similarity 0.63
Abstract · 31 pages, 6 figures

A hereditary graph class is small if it contains at most $n!c^n$ labelled graphs on $n$ vertices for some constant $c$. Small classes include proper minor-closed classes and classes of bounded twin-width. We prove that every small class has linear neighbourhood complexity, that is, in every graph in the class, vertex neighbourhoods intersect any $k$-vertex set in only $O(k)$ distinct ways. This resolves a conjecture of Bonnet, Duron, and the first two authors (ITCS 2025) and makes the algorithmic, structural, and representation consequences of linear neighbourhood complexity available for every small class. In particular, every small class admits an adjacency labelling scheme with $O(\log^2 n)$-bit labels, improving the previous $O(\log^3 n)$ bound.

0.22

Characterizing Fixed-Treewidth Planar Graphs

cs.DM math.CO ·2026-11-10 ·Laura Merker, Samuel Schneider, Torsten Ueckerdt
similarity 0.63
Abstract

We give the first inductive characterization of planar graphs of treewidth $k$ for each $k \geq 3$. Our definition generalizes the well-known inductive definition of planar $3$-trees and the recent definition of so-called planar quasi-$4$-trees [Förster, 2024]. As a key step, which may be of independent interest, we show that every planar triangulation $G$ of treewidth $k$ admits a tree decomposition of width $k$ where each adhesion set induces a cycle in $G$. As an application of planar quasi-$4$-trees, we show that planar graphs of treewidth at most $4$ have vertex arboricity at most $2$. That is, the vertex-set of every planar graph of treewidth at most $4$ can be partitioned into two sets that each induce a forest.

0.19

Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes

cs.DM math.CO ·2026-11-18 ·Vida Dujmović, Robert Hickingbotham, Pat Morin, David R. Wood
theory similarity 0.62
Abstract · 28 pages, 4 figures, written by humans

We show that, for all positive integers $t$ and $Δ$, there exists an integer $c$ such that, for every $K_t$-minor-free graph $G$ with maximum degree at most $Δ$, there exists a graph $H$ of treewidth at most $3$ and a path $P$ such that $G$ is isomorphic to a subgraph of the strong product $H\boxtimes P\boxtimes K_c$. This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of $H$ independently of $t$ and $Δ$. As an immediate consequence we obtain a bound of $O(r^4)$ on the $r$-weak colouring number of bounded-degree graphs from any proper minor-closed graph class.

0.18