I like the idea of inverting the graph. I think the problem can be converted, to coloring the (inverted) graph for which each color appears exactly twice, or just once but then only on selected vertices (a joker vertex).
If the original inverted graph contains a 3-clique, then one of the vertices of the clique can be selected and be allowed (but not necessarily) to be colored with a color not appearing anywhere else in the graph. You can repeat this step, until the graph does not contain any 3-clique anymore, that does not have a selected vertex. I think it is not difficult to prove that a coloring in the converted problem can be used to construct a coloring in the original problem and vice versa.
With the converted problem, you eliminate any vertex that has 1 or 2 edges. In case of 1 edge, you remove the vertex and its neighbor. In case of 2 edges, you contract. By contraction, you can create a new 3-clique. However, in the converted problem, you are not allowed to color that with one color (that is why the conversion is necessary, because it allows the contraction).
A cycle with an odd number of vertices, will end up in a single vertex, in which it becomes clear that a coloring is not possible. But not all impossible colorings will end up like that.
Finally, you can do a BFS. For the search-border, you have a set of possibilities. Each element of the set, specifies for every vertex on the border, whether it needs another vertex of the same color or not. You want the keep the search border small.
It might be NPC. For that, consider the vertices on the search-border as propositional variables and prove that any propositional expression can expressed as such graph (I don't know if that is possible).