The algorithm is: pick an edge $x y_1$. Inductively find a $\Delta+1$ colouring $\phi$ of $G \setminus \{ x \to y_1 \}$.
For every vertex, there is a colour which is not used at that vertex, because the degree of the vertex is $\leq \Delta$ but we have $\Delta+1$ colours to choose from.
Let $c$ be a colour missing from vertex $x$, and $c_1$ missing from $y_1$.
Then if $c_1$ is missing at $x$, we are done: colour the edge $x y_1$ with colour $c_1$.
Otherwise, $c_1$ is not missing at $x$, so there is some $y_2$ in the neighbourhood $\Gamma$ of $x$ with $\phi(x \to y_2) = c_1$.
Repeat: given $y_1, \dots, y_k \in \Gamma(x)$ distinct, and distinct colours $c_1, \dots, c_k$ such that $c_i$ is missing at $y_i$ for all $i$, and $\phi(x y_i) = c_{i-1}$, do the following: if $c_k$ is missing at $x$, stop and recolour $x y_i$ with colour $c_i$. Otherwise, let $y_{k+1} \in \Gamma(x)$ be such that $\phi(x y_{k+1}) = c_k$, and let $c_{k+1}$ be a colour missing at $y_{k+1}$.
This process builds a list of distinct $y_i$ and $c_i$, so eventually it must terminate: it can only terminate if we find $c_{k+1}$ which has already appeared as an earlier $c_i$.
Wlog $c_1 = c_{k+1}$, because we can recolour $x y_j$ with colour $c_j$ for $1 \leq j \leq i-1$ and un-colour $x y_i$ itself.
Consider the subgraph of $G$ which is coloured only in colours $c_1, c$ (recalling that $c$ is the colour missing at $x$).
The maximum degree of this subgraph is $2$, so its components are paths and cycles; but $x, y_1, y_{k+1}$ all have degree $1$ in this subgraph and so must not lie in the same component.
If $x, y_1$ are disconnected in the subgraph, swap $c, c_1$ on the $c, c_1$-component of $y_1$, and let $\phi(x, y_1) = c$.
Otherwise, $x, y_{k+1}$ are disconnected in the subgraph, so swap $c$ and $c_1$ on the $c, c_1$-component of $y_{k+1}$, and recolour $x y_{k+1}$ by $c$, $x y_i$ by $c_i$ for each $i \in [1, k]$.
This type of coloring is called a vertex-edge-face coloring in this paper, where the same conjecture is made: that for any planar graph $G$ with maximum degree $\Delta$,
$$
\chi^{vef}(G) \le \Delta + 4,
$$
where $\chi^{vef}$ is the vertex-edge-face chromatic number. (Actually, the paper's Conjecture 1 goes further and makes this conjecture for list coloring.) Furthermore, the paper proves this when $\Delta \ge 12$.
There are a couple of ways to prove the weaker result that $\chi^{vef}(G) \le \Delta + 7$: either
- By combining Theorem 1 of this paper (due to Borodin) that $\chi^{vf}(G) \le 6$ for planar graphs, with Vizing's theorem that $\chi^e(G) \le \Delta+1$ for all graphs, or
- By combining Theorem 2 of this paper (due to Waller) that $\chi^{ef}(G) \le \Delta+3$ for planar graphs, with the four-color theorem that $\chi^v(G) \le 4$ for planar graphs.
Best Answer
It is only possible for powers of $2$.
Suppose that one of the $d$ colors is red. We know that every vertex has exactly one red neighbor. So if you go through all $2^d$ vertices and, for each vertex $v$, draw an arrow from $v$ to its red neighbor, you will draw $2^d$ arrows. (Edges between two red vertices will have two arrows, one pointing each way.)
However, each red vertex has exactly $d$ arrows pointing to it: one from each of its neighbors! Since there are $2^d$ arrows, there are exactly $\frac{2^d}{d}$ red vertices. So $2^d$ must be divisible by $d$, which means $d$ must be a power of $2$.
The solution to the "Devil's Chessboard puzzle" also gives us a way to color the graph, when $d$ is a power of $2$.
Number the colors $0, 1, 2, \dots, d-1$. For each vertex $\mathbf b = (b_0, b_1, \dots, b_{d-1})$, let $I_{\mathbf b} = \{i : b_i = 1\}$: the set of positions that are $1$ in the vertex. Compute the number $n_{\mathbf b}$ obtained by a bitwise XOR of every element of $I_{\mathbf b}$, and color $\mathbf b$ with the color corresponding to that number.
For every $\mathbf b$, to the neighbor that differs from $b$ in the $i^{\text{th}}$ coordinate has the color corresponding to $n_{\mathbf b} \oplus i$ (where $i$ is bitwise XOR). As $i$ ranges over $0$ to $d-1$, so does $n_{\mathbf b} \oplus i$, so we see all the colors on the neighbors of $\mathbf b$.
(This only works for powers of $2$, because only in that case is $n_{\mathbf b}$ limited to the range $0, 1, \dots, d-1$.)