# The equivalence of a kind of 2-fold edge coloring and the 2-distance vertex coloring for subcubic graphs

Let $$G$$ be a subcubic graph.

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 $$e_1$$ and $$e_2$$ are adjacent, then $$\lvert\varphi(e_1)\cap \varphi(e_2)\rvert=1$$,
• 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)?

My feeling is that the answer is YES as no conterexample had been constructed yet.

Note that if $$G$$ admits a 2-distance vertex 4-coloring, then one can easily construct the above mentioned edge coloring.

The answer is False. Let $$G$$ be the Möbius ladder on 12 vertices with every edge subdivided, or in SageMath code,

>G=Graph('K?AEF@oM?w@o')   #Mobius ladder on 12 vertices
>G.subdivide_edges(G.edges(),1)


$$G$$ is a subcubic graph.

>max(G.degree())
3


If the line graph of $$G$$ admits a 2-distance vertex 4-coloring $$\psi$$ with colors in $$\{1,2,3,4\}$$, then the graph $$G$$ admits the edge coloring you have mentioned, by coloring each edge $$e$$ by the pair $$\{\psi(e), 5\}$$.

SageMath shows that there's such a coloring.

>l=G.line_graph()
>l=l.distance_graph([1,2])
>l.chromatic_number()
4


But the graph $$G$$ has no 2-distance vertex 4-coloring.

>d=G.distance_graph([1,2])
>d.chromatic_number()
5