{"id":"arxiv/2610.35794","url":"https://arxiv.org/abs/2610.35794","tags":["cs.CC","math.CO"],"score":0,"title":"Computational complexity of the $H$-coloring problem in cubic graphs","domain":"cs.CC","source":"arxiv","authors":["Vahan Mkrtchyan"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{}}