Computational complexity of the H-coloring problem in cubic graphs
Abstract
If G and H are two cubic graphs, then an H-coloring of G is a mapping f: E(G)→ E(H), such that for every v∈ V(G) there is a vertex x∈ V(H), such that f(∂G(v))=∂H(x). If G admits an H-coloring then it is common to write H≺ 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≺ G. A conjecture by Hakobyan and the author states that H-coloring is polynomial time solvable, if H does not admit a P12-coloring. Here P12 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≠ NP, by showing that S6-coloring is NP-complete. Here S6 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*(cn), where H is a simple connected cubic graph, n is the number of vertices of the input cubic graph G and c=√8≈ 2.8284.
Related
- Two-coloring cubic graphs with small monochromatic components, but without singletons
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
- A variety of the mutual-visibility coloring problem for graphs
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
- Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
BibTeX
@misc{mkrtchyan2026computational,
title = {{Computational complexity of the $H$-coloring problem in cubic graphs}},
author = {Vahan Mkrtchyan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35794},
eprint = {2610.35794},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35794},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Computational complexity of the H-coloring problem in cubic graphs
AU - Vahan Mkrtchyan
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35794
UR - https://arxiv.org/abs/2610.35794
AB - If G and H are two cubic graphs, then an H-coloring of G is a mapping f: E(G)→ E(H), such that for every v∈ V(G) there is a vertex x∈ V(H), such that f(∂_G(v))=∂_H(x). If G admits an H-coloring then it is common to write H≺ 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≺ 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≠ 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=√8≈ 2.8284.
ER -