Answers are grounded in this paper and cite their sources.
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₁₂-coloring. Here P₁₂ 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₆-coloring is NP-complete. Here S₆ 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ⁿ), 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.
No takes yet. Share an insight, caveat, or question.
Vahan Mkrtchyan (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: