CS Paper Radar

Computational complexity of the $H$-coloring problem in cubic graphs

Vahan Mkrtchyan

cs.CC math.CO ·submitted 2026-10-26 17:30 UTC · v1
hot direction

Abstract

If $G$ and $H$ are two cubic graphs, then an $H$-coloring of $G$ is a mapping $f: E(G)\rightarrow E(H)$, such that for every $v\in V(G)$ there is a vertex $x\in V(H)$, such that $f(\partial_G(v))=\partial_H(x)$. If $G$ admits an $H$-coloring then it is common to write $H\prec G$. In this paper, for a fixed connected cubic graph $H$, we consider a decision problem, which we call $H$-coloring. In this problem, on the input one is given a connected cubic graph $G$. The goal is to decide whether $H\prec G$. A conjecture by Hakobyan and the author states that $H$-coloring is polynomial time solvable, if $H$ does not admit a $P_{12}$-coloring. Here $P_{12}$ is the unique cubic graph obtained from the Petersen graph by expanding one of its vertices into a triangle. In this paper, we disprove this conjecture under $P\neq NP$, by showing that $S_6$-coloring is NP-complete. Here $S_6$ is the unique cubic graph on six vertices having exactly one bridge. Our second result is an algorithm that solves $H$-coloring problem in time $O^*(c^n)$, where $H$ is a simple connected cubic graph, $n$ is the number of vertices of the input cubic graph $G$ and $c=\sqrt{8}\approx 2.8284$.

Comment
13 pages, 9 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Three-edge-coloring apex cubic graphs

cs.CG math.COcs.DMcs.DS ·2026-08-24 ·Yuta Inoue, Ken-ichi Kawarabayashi, Rintaro Matsuo, Atsuyuki Miyashita, Bojan Mohar +1 more
theorycode/data similarity 0.73
Abstract · We provide detailed pseudocode specifying the computer-assisted parts of the proof. Each pseudocode is linked to the corresponding function …

A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, generalizes that of the Four Color Theorem, which requires computer checks. As in the previous proof of the Four Color Theorem, the proof is constructive. More precisely, given a $2$-connected apex cubic graph $G$ on $n$ vertices, our reducibility and discharging procedure yields a three-edge-coloring of $G$ in $O(n^2)$ time. As an additional reproducibility check for our computer checks, independent implementations reconstructed from the detailed pseudocode (given in the appendix) using generative AI systems reproduced the required computational results. These reconstructions are not part of the mathematical justification of the theorem, but provide additional evidence for the reproducibility of the computations.

0.43

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

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

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

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.67
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

Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path

cs.CC cs.DMmath.CO ·2026-11-10 ·Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt
similarity 0.67
Abstract

We examine the computational complexity of well-known problems on subgraphs of the strong product of two paths. Namely, for Max Cut we show NP-hardness on induced subgraphs of $P \boxtimes P$ answering a question by Dvořák, Huynh, Joret, Liu, and Wood (2021). For 3-Edge Coloring we show NP-hardness on subgraphs of $P \boxtimes P$ and that it is equivalent to 3-Edge Coloring on planar graphs for induced subgraphs of $P \boxtimes P$. It is a long standing open question whether 3-Edge Coloring on planar graphs is NP-hard. As a second contribution, we consider graphs of the form $G \boxtimes P$ and show that Feedback Vertex Set on these graphs is FPT in the clique-width of $G$. Furthermore, we show that it can be solved in polynomial time if $G$ is chordal or co-comparable and that the computational complexity depends on the parity of $P$ if $G$ is bipartite. Namely, it is solvable in polynomial time if $P$ has an even number of vertices but is NP-complete otherwise. For Max Cut, we show that it can be solved in polynomial time if $G$ is bipartite.

0.07

Nullstellensatz degree under Hajós joins and vertex identifications

cs.CC math.CO ·2026-09-14 ·Ying Xie
similarity 0.66
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

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

List 3-Coloring in tame classes of graphs in quasipolynomial time

cs.DS math.CO ·2026-10-30 ·Paweł Rzążewski
similarity 0.65
Abstract

A class of graphs $\mathcal{G}$ is tame if there is a constant c such that every $n$-vertex graph in $\mathcal{G}$ has at most $n^c$ minimal separators. Many important graph classes are tame, including chordal graphs, permutation graphs, and circle graphs. Several fundamental problems, most notably Max Weight Independent Set, can be solved in polynomial time on every tame class, which explains in a unified way their tractability on all these classes. We show that List 3-Coloring can be solved in quasipolynomial time on every tame class of graphs.

0.26