A note on $\bar{X}$-coloring and $\hat{A}$-coloring 4-regular graphs

Abstract

Let ${\partial }_H(u)$ be the set of edges incident with a vertex $u$ in the graph $H$. We say that a graph $G$ is $H$-colorable if there exist total functions $f:E(G)\to E(H)$ and $g:V(G)\to V(H)$ such that $f$ is a proper edge-coloring of $G$ and for each vertex $u\in V(G)$ we have $f({\partial }_G(u))={\partial }_H(g(u))$. Let $\bar{X}$ be the graph obtained by adding three parallel edges between two degree one vertices of the graph $K_{1,4}$. Let $\hat{A}$ be the graph obtained by adding two pendant edges to two different vertices of a triangle and then adding two edges between the degree two vertex and the two adjacent degree three vertices. Malnegro and Ozeki [Discrete Math. 347(3):113844 (2024)] asked whether every 4-regular graph with an even number of vertices and an even cycle decomposition of size 3 admits an $\bar{X}$-coloring or an $\hat{A}$-coloring and whether every 2-connected planar 4-regular graph with an even number of vertices admits such a coloring. Additionally, they conjectured that for every 2-edge-connected simple cubic graph $G$ with an even number of edges, the line graph $L(G)$ is $\bar{X}$-colorable. In this short note, we discuss two algorithms for deciding whether a graph $G$ is $H$-colorable. We give a negative answer to the two questions and disprove the conjecture by finding suitable graphs, as verified by two independent algorithms.

6 pages, 3 figures