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

Question

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.

Answer 1

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