CS Paper Radar

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

Iain Beaton, Ben Cameron, Adam van Omme

cs.DM math.CO ·submitted 2026-10-07 18:08 UTC · v1

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

Closest papers

Nearest neighbours by meaning across the whole index.

Parameterized complexity of $k$-Coloring in graphs with no long induced paths

cs.DS ·2026-08-18 ·Paweł Rzążewski
theory similarity 0.73
Abstract

We study the parameterized complexity of (List) $k$-Coloring in $H$-free graphs, where $H$ is a linear forest, that is, a disjoint union of paths. First, considering $k$ as the parameter, we establish the following: * For any $s \geq 0$, List $k$-Coloring in $(P_4+sP_1)$-free graphs is fixed-parameter tractable (FPT). * $k$-Coloring is W[1]-hard in $2P_2$-free graphs. The second result settles, in a strong form, a long-standing open problem posed by Hoàng, Kamiński, Lozin, Sawada, and Shu [Algorithmica, 2010]. Next, we prove that $k$-Coloring is NP-hard in $(P_4+P_2)$-free graphs. These three findings, together with known results from classical, non-parameterized complexity, yield a complete complexity classification of $k$-Coloring and List $k$-Coloring in $H$-free graphs, parameterized by $k$, into the cases: FPT, XP but W[1]-hard, and paraNP-hard. We also prove that $3$-Coloring is W[1]-hard in $P_t$-free graphs when parameterized by $t$. This answers a question of Golovach, Johnson, Paulusma, and Song [Journal of Graph Theory, 2017]. Finally, as a byproduct of our algorithm for List $k$-Coloring in $(P_4+sP_1)$-free graphs, we show that, for every fixed $s$ and $k$, there are only finitely many $(P_4+sP_1)$-free minimal obstructions to $k$-colorability. This settles a conjecture of Cameron, Hoàng, and Sawada [Disc. Appl. Math., 2022] and completes the dichotomy concerning the finiteness of the family of vertex-$k$-critical $H$-free graphs for every graph $H$ and every $k$.

0.20

Complexity and algorithms for proper conflict-free coloring in graphs

cs.DM math.CO ·2026-08-11 ·Dinabandhu Pradhan, Vaishali Sharma
similarity 0.69
Abstract

A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every non-isolated vertex $v\in V(G)$. The PCF chromatic number, denoted by $χ_{pcf}(G)$, is the least integer $k$ such that there exists a PCF $k$-coloring of $G$. Given a graph $G$ and a positive integer $k$, PCF $k$-COLORABILITY is to decide whether $G$ admits a PCF $k$-coloring. Ahn et al. [Discrete Appl. Math. 377 (2025) 10-17] proved that PCF $k$-COLORABILITY is NP-complete for bipartite graphs. We strengthen this result by proving that PCF $k$-COLORABILITY is NP-complete for perfect elimination bipartite graphs, which is a proper subclass of bipartite graphs. We also show that the PCF chromatic number of a graph cannot be approximated within $O(n^{1-\varepsilon})$ unless P=NP, for any $\varepsilon>0$. On the positive side, we provide linear-time algorithms for PCF $k$-COLORABILITY in block graphs, proper interval graphs, chain graphs, and pseudo-split graphs. We show that $χ_{pcf}(G)\leq ω(G)+1$ for block graphs, proper interval graphs, and pseudo-split graphs (except $C_5$), and we characterize all graphs for which the equality holds.

0.41

Elementary graphs are chromatic-choosable

cs.DM math.CO ·2026-10-12 ·Narayanan N, Nandana K. Vasudevan, K. Somasundaram
theory similarity 0.68
Abstract · 13 page, 5 figures, 1 table

A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$, confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray--Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.

0.34

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

Nullstellensatz degree under Hajós joins and vertex identifications

cs.CC math.CO ·2026-09-14 ·Ying Xie
similarity 0.68
Abstract

We study the minimum coefficient degree $N_{k,\F}(G)$ of a Nullstellensatz certificate for Bayer's $k$-coloring equations, where the characteristic of $\F$ does not divide $k$. If $J$ is a \HJ\ join of non-$k$-colorable graphs $G,H$ and $m=\max\{N_{k,\F}(G),N_{k,\F}(H)\}$, then $N_{k,\F}(J)\leq m+k$. When deletion of the selected edge makes each input $k$-colorable, we also have $N_{k,\F}(J)\geq m$; the degree congruence then gives $N_{k,\F}(J)\in\{m,m+k\}$. This partially answers a question of Li, Lowenstein, and Omar. For three-coloring over $\F_2$, we construct an infinite $4$-critical family of exact degree seven, attaining the bound at input degree four. In contrast, every graph constructed from $K_4$ solely by \HJ\ joins has degree $O(\log n)$ and a certificate with polynomially many terms: joins preserve treewidth at most three, and balanced separators yield low-degree certificates. Additional vertex identifications are excluded from this obstruction. We classify all single identifications of the $25$-vertex base graph; exactly $36$ preserve degree seven, producing $24$-vertex $4$-critical graphs of treewidth four. A compressed self-join at adjacent true twins prevents degree loss and gives a repeatable rule adding four vertices per round. The rule does not establish degree amplification or preservation of criticality. Exact witnesses and standalone verification programs accompany the finite results.

0.09

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

Kempe Reachability with $k\geq 3$ Colors Is $\mathsf{PSPACE}$-Complete on Claw-Free Graphs

cs.DS cs.DM ·2026-10-22 ·Duc A. Hoang
similarity 0.66
Abstract

A \emph{proper vertex coloring} assigns colors to vertices so that adjacent vertices have distinct colors. A \emph{Kempe change} in a proper vertex coloring exchanges two colors on one component of the subgraph induced by the vertices of those colors. For a fixed palette of $k$ colors, \textsc{Kempe Reachability} asks whether two given proper vertex colorings of the same graph are connected by a sequence of Kempe changes. This problem is known to be $\mathsf{PSPACE}$-complete for every fixed $k\geq 3$. A graph is \emph{claw-free} if no vertex has three pairwise nonadjacent neighbors. The \emph{line graph} of a graph has one vertex for each edge, with two vertices adjacent exactly when the corresponding edges share an end. Line graphs are claw-free, and their Kempe changes correspond to \emph{edge-Kempe changes} in the original graph, which exchange two colors on one component of the subgraph formed by the edges of those colors. A claw-free graph with a proper $k$-coloring has maximum degree at most $2k-2$, whereas for $k\geq 4$ all proper $k$-colorings of a graph of maximum degree at most $k$ are connected by Kempe changes. We show that, for every fixed $k\geq 3$, \textsc{Kempe Reachability} with $k$ colors is $\mathsf{PSPACE}$-complete even on line graphs of connected simple $k$-regular graphs, and hence even on connected $(2k-2)$-regular claw-free graphs. Equivalently, deciding whether two proper $k$-edge-colorings are connected by edge-Kempe changes is $\mathsf{PSPACE}$-complete even on connected simple $k$-regular graphs. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.

0.26

Claw-free perfect graphs are chromatic-choosable

cs.DM math.CO ·2026-10-31 ·Suchismita Mishra, Narayanan Narayanan, Umesh Shankar
theory similarity 0.66
Abstract · 33 pages, 8 figures

We prove that every claw-free perfect graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$. More strongly, if $S$ is a clique of simplicial vertices of $G$ and $k\geω(G)$, every proper precoloring of $S$ extends to a proper coloring of $G$ from arbitrary lists of size $k$ on $V(G)\setminus S$. The proof has three coloring steps: a mixed-list theorem for cobipartite graphs, a precoloring-extension theorem for elementary graphs built on Galvin's kernel method and a homogeneous-pair exchange argument, and a polynomial method (Combinatorial Nullstellensatz) argument for graphs of interval type in which a Vandermonde factor is transferred across each incomplete pair. The three coloring steps are assembled along the structure theorems of Chvátal--Sbihi, Maffray--Reed and Chudnovsky--Seymour, using double clique cutsets for composition. As a consequence, every perfect line graph is chromatic-choosable, recovering the theorem of Peterson and Woodall. Our precoloring extension theorem also resolves a conjecture posed by Chudnovsky and Seymour.

0.24