CS Paper Radar

List packing for graphs with small arboricity

Stijn Cambie, Wouter Cames van Batenburg, Xuding Zhu

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

Abstract

We prove that every graph $G$ whose edge set is the union of $r$ forests has list packing number at most $2^r$. This means that for all $k\ge 2^r$ and every list-assignment $L$ with lists of size $k$, the graph $G$ admits $k$ disjoint proper $L$-colourings. While for large $r$ this bound is far from optimal, for $r\in\{1,2\}$ it is sharp. As a direct corollary of the case $r=2$, we obtain that every triangle-free planar graph has list packing number at most $4$, thus improving upon a result of Dvořák, Masařík, Musílek and Pangrác and providing the optimal answer to a question of Dvořák, Postle and Norin on (weighted) $ε$-flexibility of such graphs. As a corollary of the case $r=3$, we obtain a short alternative proof that every $K_5$-minor-free (and hence every planar) graph has list-packing number at most $8$, matching the state of the art. All results above also hold for the stronger notion of correspondence packing.

Comment
10 pages (of which 2 for the main proofs)

Closest papers

Nearest neighbours by meaning across the whole index.

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

Large diameter for $(Δ+2)$-colouring reconfiguration

cs.DM math.CO ·2026-11-12 ·Wouter Cames van Batenburg
similarity 0.68
Abstract · 15 pages, 2 figures

Given a graph $G$ and an integer $k$, the reconfiguration graph $\mathcal{R}_{k}(G)$ has the proper $k$-colourings of $G$ for vertices, two of which are adjacent if and only if they differ on precisely one vertex of $G$. In $2022$, Cambie, Cranston and the author proved that the diameter of $\mathcal{R}_{Δ+2}(G)$ is at most $n+2μ$, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of $\mathcal{R}_{Δ+2}(G)$ is precisely equal to $n + μ$, for every graph $G$ with $n$ vertices, matching number $μ$ and maximum degree $Δ$. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least $n+\frac{3}{2}μ-2$. We also provide counterexamples that are $Δ$-regular, we show that every graph has reconfiguration diameter at least $n+\frac{1}{2} μ$, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.

0.25

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

Characterizing Fixed-Treewidth Planar Graphs

cs.DM math.CO ·2026-11-10 ·Laura Merker, Samuel Schneider, Torsten Ueckerdt
similarity 0.67
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

What remains of the planar induced minor conjectures?

cs.DM cs.CCcs.DSmath.CO ·2026-11-06 ·Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski
similarity 0.66
Abstract · 26 pages, 7 figures

Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph $H$, Maximum Weight Independent Set and List $3$-Coloring are polynomial-time solvable in $H$-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is $\mathsf{NP}$-hard in graphs excluding the $5\times5$ grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several $16$-vertex trees, and we introduce a second, independent family of hard instances. We also prove that $3$-Coloring is $\mathsf{NP}$-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless $\mathsf{NP}\subseteq\mathsf{QP}$. On the structural side, we identify planar graphs $H$ for which the structural conjecture holds, while the algorithmic one fails. Thus, constantly dominated balanced separators cannot by themselves explain the tractability of Maximum Weight Independent Set and List $3$-Coloring.

0.15

A proof of Wang's planar $D$-coloring conjecture

cs.DM math.CO ·2026-10-23 ·Harshit Verma
theory similarity 0.66
Abstract · 22 pages, 3 figures. Ancillary files contain the certificates and verification scripts for the computer-assisted case of maximum degree 6

We prove Wang's planar $D$-coloring conjecture. A $D$-coloring of a graph is a proper edge coloring in which every subgraph isomorphic to $K_4$ minus an edge is rainbow. Wang conjectured that every planar graph of maximum degree $Δ$ has a $D$-coloring with $9$ colors if $Δ=4$, $10$ colors if $Δ=5$, and $2Δ-1$ colors if $Δ\ge6$. Hu, Kong and Wang proved the cases $Δ\le5$ and $Δ\ge33$. We prove the sharp bound $2Δ-1$ for every $Δ\ge6$, settling the remaining cases. The proof uses discharging; the case $Δ=6$ is computer-assisted.

0.10

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.66
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.23

Packing Diverse Shortest Cycles

cs.DS ·2026-10-07 ·Akanksha Agrawal, Fedor V. Fomin, Petr A. Golovach, Vinod Gupta, Yash Hiren More +1 more
theory similarity 0.65
Abstract

Bentert, Fomin, Golovach, Korhonen, Lochet, Panolan, Ramanujan, Saurabh, and Simonov (SODA 2025) initiated the parameterized study of Edge-Disjoint Shortest Cycle Packing: given a weighted graph $G$ and an integer $k$, decide whether $G$ contains $k$ edge-disjoint cycles of minimum weight. They showed that the problem admits an algorithm running in time $n^{O(k^6)}$ and asked whether it is fixed-parameter tractable or $W[1]$-hard parameterized by $k$. We resolve this question by proving that Edge-Disjoint Shortest Cycle Packing is $W[1]$-hard parameterized by $k$, even on unweighted subcubic graphs. The same lower bound also applies to the vertex-disjoint variant. For planar graphs, they provides a construction of a kernel with $O(k^2)$ vertices and an algorithm running in time $k^{O(k)} \cdot n^{O(1)}$, and explicitly asked whether the problem admits a single-exponential algorithm of running time $2^{O(k)} \cdot n^{O(1)}$. Rather than addressing this question in isolation, we introduce a more general framework, Diverse Shortest Cycle Coverage, which asks for $k$ shortest cycles that may overlap in a controlled way while maximizing the total weight of covered edges. This framework simultaneously captures edge-disjoint shortest cycle packing, the problem of finding diverse shortest cycles, and the problem of maximizing edge coverage by shortest cycles. Our main algorithmic result shows that Diverse Shortest Cycle Coverage can be solved on planar graphs in time $2^{O(k)} \cdot n^{O(1)}$, thereby giving a single-exponential algorithm for Edge-Disjoint Shortest Cycle Packing as a special case. The key idea of our algorithm is a structural analysis of the Laminar Shortest Cycles Tree, a tree-like decomposition that reveals a laminar interaction pattern among shortest cycles in planar graphs and enables an efficient dynamic programming algorithm.

0.24