Careful 5COLOR NP hardness

Question

Given the following definition of Careful 5COLORING:

A 5-coloring is careful if the colors assigned to adjacent vertices are not only distinct, but differ by more than 1(mod 5)

how would a reasonable reduction to prove NP hardness work? Suggestion is to reduce from standard 5COLOR, but I am not able to find a correct one.

I have tried reducing from an instance $G$ of the standard 5COLOR as suggested creating one extra vertex between every edge in $G$. That is, let $\{u,v\}$ be an edge in $G$, create a new vertex $w$ and add edges $\{u,w\}$ and $\{w,v\}$. Fix the color of every new vertex to the same color, for example 3. This results in a new graph $H$.

When proving "$G$ is 5COLORABLE iff $H$ is carefully 5COLORABLE", I can prove the first $G$ is 5COLORABLE $\rightarrow$ $H$ is carefully 5COLORABLE since $H$ actually requires only 3 colors (if every new vertex is colored as 3, I only need colors 1 and 5 for the original vertexes in $G$).

On the other hand, the proof doesn't work since there are instances where $G$ isn't 5COLORABLE but $H$ is carefully 5COLORABLE. This has led me to believe my reduction is wrong.

Answer 1

There is a dichotomy theorem that covers this. For a graph $H$, let $P_H$ be the following problem: On input of graph $G$, decide whether there is a homomorphism from $G$ to $H$. A homomorphism is a function that maps vertices of $G$ to vertices of $H$ in such a way that edges of $G$ are mapped to edges of $H$.

Observe how $5$-colouring is $P_{K_5}$, where $K_5$ is the complete graph with $5$ vertices: The only constraint for a homomorphism to $K_5$ is that the endpoints of edges are mapped to different vertices. Furthermore, careful $5$-colouring is $P_{C_5}$, where $C_5$ is a cycle of length $5$. (To see how that works out, let the vertices of said cycle be in the order $0,2,4,1,3$.)

Now the theorem states that:

1. If $H$ is bipartite, then $P_H$ is in PTIME.
2. If $H$ is not bipartite, then $P_H$ is NP-complete.

If you still want a reduction from $5$-colouring, I suggest to look for a suitable gadget. The gadget should be a graph $I$ with two special vertices $v$ and $w$, such that

1. There is no careful $5$-colouring of $I$ that assigns the same colour to $v$ and $w$.
2. For all colours $c$ and $d$ such that $c\not=d$, there is a careful $5$-colouring of $I$ that assigns $c$ to $v$ and $d$ to $w$.

Then, for a reduction you would replace every edge with a copy of $I$.

[EDIT]

Wikipedia has the following reference for the dichotomy theorem:

Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110