CS Paper Radar

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

Duc A. Hoang

cs.DS cs.DM ·submitted 2026-10-22 13:37 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Claw-free perfect graphs are chromatic-choosable

cs.DM math.CO ·2026-10-31 ·Suchismita Mishra, Narayanan Narayanan, Umesh Shankar
theory similarity 0.70
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

Complexity and algorithms for proper conflict-free coloring in graphs

cs.DM math.CO ·2026-08-11 ·Dinabandhu Pradhan, Vaishali Sharma
similarity 0.68
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

Graph Coloring with Color Preferences

cs.GT math.CO ·2026-09-01 ·Tomohiro Koana, Yeeseok Oh, Hirotaka Yoneda
theory similarity 0.68
Abstract

We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its original one. We define the stable chromatic number $χ_\mathrm{stable}(G)$ of a graph $G$ as the minimum integer $k$ such that every preference profile admits a stable $k$-coloring of $G$. We establish several upper and lower bounds. In particular, for any acyclic orientation of the edges of $G$, the largest number of vertices reachable from a vertex by directed paths, including the vertex itself, is an upper bound on $χ_\mathrm{stable}(G)$. This shows that $χ_\mathrm{stable}(G)$ is well-defined. We also show that $O(t \log (1+n/t))$ colors suffice for an $n$-vertex graph $G$ of treewidth $t$, and complement this with a lower bound in terms of the Grundy number. Turning to the problem of finding a minimum stable coloring for a given profile, we show that stable $2$-colorability is polynomial-time solvable, whereas stable $k$-colorability is NP-complete for every fixed $k\ge 3$. Using the treewidth bound, we give a fixed-parameter tractable algorithm parameterized by treewidth.

0.16

Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs

cs.DM math.CO ·2026-11-04 ·Gautam K. Das, Kamal Santra
theory similarity 0.67
Abstract

A proper conflict-free coloring is a proper coloring in which each nonisolated vertex has a neighbor whose color occurs exactly once in its open neighborhood. We prove that deciding whether the clique number of colors suffices is NP-complete on undirected path graphs, even with a supplied representation by paths in a star. One extra color suffices on every instance in the reduction. We also prove NP-completeness on chordal bipartite graphs for every fixed palette size $k\ge4$. For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in $O(n+m)$ time, where $n$ and $m$ count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most $s$, we give an exact algorithm in $n^{2^{O(s+1)}}$ time, with no bound on the clique number.

0.12

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

Elementary graphs are chromatic-choosable

cs.DM math.CO ·2026-10-12 ·Narayanan N, Nandana K. Vasudevan, K. Somasundaram
theory similarity 0.65
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

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

cs.DS ·2026-08-18 ·Paweł Rzążewski
theory similarity 0.64
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

Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.64
Abstract

Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.

0.16