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)?


1 Answer 1


The answer is false.

Let $G$ be the 3-prism and $\varphi$ the coloring shown below.

coloring of G

$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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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