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.


1 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$ is a subcubic graph.


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.