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.