CS Paper Radar

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

Vida Dujmović, Robert Hickingbotham, Pat Morin, David R. Wood

cs.DM math.CO ·submitted 2026-11-18 14:50 UTC · v1
theory

Abstract

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.

Comment
28 pages, 4 figures, written by humans

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.71
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.08

Tight B-Trees for Adjacency Labeling

cs.DS cs.DM ·2026-11-08 ·Noy Rotbart
similarity 0.68
Abstract · 8 pages, 2 figures

We show that planar graphs admit adjacency labels of size $\log n+O(\log\log n)$: every vertex gets a label of this many bits, and the adjacency of two vertices is decided from their labels alone, in constant time. This improves the $\log n+O(\sqrt{\log n\log\log n})$ of Dujmović et al. (J. ACM 2021) and the $\log n+O(\sqrt{\log n})$ of Gawrychowski and Janczewski (SOSA 2022). Equivalently, $n$-vertex planar graphs have an induced-universal graph with $n(\log n)^{O(1)}$ vertices, down from $n2^{O(\sqrt{\log n})}$. The same holds for graphs of bounded genus, apex-minor-free graphs and $k$-planar graphs. For every proper minor-closed class we get $\log n+O(\sqrt{\log n\log\log n})$, down from the $\log n+O((\log n)^{3/4})$ of Dujmović et al. (2026). Both results come from tight B-trees: nodes are split into parts of nearly equal size, so every node but the topmost stays within a factor $1\pm O(1/\log n)$ of its target size, and a root-to-leaf path loses only $O(\log\log n)$ bits.

0.24

An improved bound on the treewidth of planar graphs excluding a grid minor

cs.DM math.CO ·2026-09-14 ·Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret, Robin Petit, Jean-Florent Raymond +1 more
similarity 0.68
Abstract

We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4t +4$. This improves on the previously best known bound of $\frac{9}{2}t - \frac{11}{2}$, due to Gu and Tamaki (2012), and is within a factor $2$ of optimal. A key step in the proof is showing the following result, which might be of independent interest: Every $2$-connected plane graph $G$ with radius $d$ and faces of size at most $k$ has a tree-decomposition of width at most $\max\{3d+ k+5, 2d+2k+1\}$ such that the vertex set of every face of $G$ is contained in some bag.

0.41

Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

cs.DS cs.DM ·2026-11-06 ·Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
similarity 0.68
Abstract

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $φ$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has treewidth at most $t$ and satisfies $φ$. This captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to graphs of any fixed bounded treewidth. We give an algorithm with running time $2^{k^{2/3} \log^{O(1)} k}n^{O(1)}$ on $H$-induced-minor-free graphs, where $k$ is the optimum deletion-set size. This resolves in the affirmative the open problem highlighted by Bonnet and Rzążewski [Algorithmica 2019] and Berthe, Bougeret, Gonçalves, and Raymond [ICALP 2025] regarding the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Our algorithm significantly improves over existing parameterized algorithms for more restricted classes of problems on more restricted classes of graphs. When the property defined by $φ$ is hereditary, we also obtain a quasi-polynomial time approximation scheme, namely an algorithm that produces a $(1+\varepsilon)$-approximate solution in quasi-polynomial time. Both the sub-exponential algorithm and the quasi-polynomial time approximation scheme build on the same new structural and algorithmic insights.

0.20

Three trees suffice for a constant stretch in minor-free graphs

cs.DS cs.CG ·2026-08-13 ·Hung Le, Huy Pham, Cuong Than, Tuan Tran
theory similarity 0.68
Abstract

In this short note, we show that $H$-minor-free graphs have a tree cover with $3$ trees and constant stretch for any fixed graph $H$. The number of trees matches the recent lower bound by Chen, Tan, and Xu who showed that a toroidal grid requires at least $3$ trees for constant stretch. Our result is obtained by establishing a connection between tree covers and Assouad--Nagata dimension and then invoking the recent dimension bound for minor-free metrics by Liu.

0.32

$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrt{n})$

cs.DM math.CO ·2026-10-31 ·Jonathan Conroy, Hung Le, Jack Spalding-Jamieson
theory similarity 0.67
Abstract

We show that every $K_h$-minor-free graph with $n$ vertices has a balanced separator of size $O(h\sqrt{n})$ for any parameter $h \in \mathbb{N}$, resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given $k$ large (not necessarily disjoint) subsets of vertices, there is a walk of length $O(k/ψ(G))$ hitting every subset, where $ψ(G)$ is the vertex expansion. This technical result substantially improves on an analogous lemma by Alon, Seymour, and Thomas [AST90] in an important parameter setting, where the previous lower bound [Kot00] does not apply.

0.48

Induced packing treewidth II. Excluding a clique or a biclique

cs.DM math.CO ·2026-09-18 ·Amir Nikabadi, Paweł Rzążewski
theory similarity 0.66
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. For a graph $H$, \emph{induced $H$-packing treewidth}, denoted by $\treepi_{H}$, is a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of $H$ intersecting that bag. This notion generalizes some previously studied parameters: when $H=P_1$, it is equivalent to tree-independence number, and when $H=P_2$, it is equivalent to induced matching treewidth. We prove the following: \begin{itemize}[itemsep=2mm,leftmargin=6mm] \item For all $a,t\in \mathbb{N}$, $K_{a,a}$-free graphs of bounded induced $P_t$-packing treewidth have bounded tree-independence number. This extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for $t=2$, and a result of Hajebi and Spirkl who showed that $(P_t,K_{a,a})$-free graphs have bounded tree-independence number. \item If $H$ is any fixed path or a star, then the class of graphs of bounded induced $H$-packing treewidth is $χ$-bounded. Again, this extends the previous result of Abrishami et al. [SIAM J. Discrete Math., 2025] for $H=P_2$. \item Finally, we study the relationship between induced packing treewidth and \emph{sim-width}, a width parameter based on branch decompositions. We show that, although \emph{sim-width} and induced $P_3$-packing treewidth are incomparable, graphs of bounded sim-width that exclude all \emph{$H$-obstructions}---certain graphs that force large induced $H$-packing treewidth---have bounded induced $H$-packing treewidth. This simultaneously generalizes and resolves questions posed by Abrishami et al. [SIAM J. Discrete Math., 2025] and Brettell et al. [European J. Comb., 2025]. \end{itemize}

0.26

Obstructions to $k$-colouring $H$-free graphs

cs.DM math.CO ·2026-10-07 ·Iain Beaton, Ben Cameron, Adam van Omme
similarity 0.66
Abstract

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. In 2020, Chudnovsky, Goedgebeur, Schaudt, and Zhong characterized all graphs $H$ such that there are only finitely many minimal obstructions to $3$-colouring $H$-free graphs. In general, the minimal obstructions to $k$-colouring $H$-free graphs are the $(k+1)$-vertex-critical $H$-free graphs, those are, the $H$-free graphs $G$ with $χ(G)=k+1$ but $χ(G-v)=k$ for every vertex in $G$. In this paper we complete the characterization for all $k > 4$ by showing that there are onky finitely $k$-vertex-critical $H$-free graphs if and only if $H$ is an induced subgraph of $P_4+\ell P_1$ for some $\ell \geq 0$.

0.20