# A sufficient condition for a subcuic graph having a 2-distance vertex 4-coloring

Let $$G$$ be a subcubic graph with only vertices of degree 1 or degree 3.

Suppose that $$G$$ has an edge coloring $$\varphi$$ using colors from $$\{1,2,3,4,5\}$$ such that

• each edge is colored with a set of two elements from $$\{1,2,3,4,5\}$$ (e.g., $$\varphi(e)=\{1,2\}$$ for some edge $$e$$),
• if $$v$$ is a vertex of degree 3 that is incidenct with edges $$e_1, e_2$$ and $$e_3$$, then there exists $$\{a,b,c\}\subseteq \{1,2,3,4,5\}$$ such that $$\varphi(e_1)=\{a,b\}$$, $$\varphi(e_1)=\{a,c\}$$, $$\varphi(e_1)=\{b,c\}$$,
• if the distance between two edges $$e_1$$ and $$e_2$$ is 2 (i.e, $$e_1$$ and $$e_2$$ are not adjacent, and there is an edge $$e_3$$ adjacent to both $$e_1$$ and $$e_2$$), then $$\varphi(e_1)\neq \varphi(e_2)$$.

Then, does $$G$$ have a 2-distance vertex 4-coloring (i.e., a proper vertex 4-coloring of $$G$$ such that every two vertices at distance 2 receive distinct colors)?

Let $$G$$ be the 3-prism and $$\varphi$$ the coloring shown below. $$G$$ cannot have a 2-distance vertex 4-coloring. As all pairs of vertices in $$G$$ have distance either 1 or 2, a 2-distance coloring of $$G$$ would require 6 colors.