Is there a sequence of vertices for which this greedy coloring algorithm works? Let $G$ be a finite graph and $X$ be a set of $\chi(G)$ colors.
Consider the following algorithm:

*

*In the $i-$th step, we color the $i-$th vertex of $G$ with a random color of $X$ different of the colors of it's neighbors.

If any of the steps cannot be performed, the algorithm fails. If all vertices can be colored, the algorithm succeeds
Is it possible to order the vertices of $G$ in such a way that this algorithm always succeeds? What if $X$ has $\chi(G)+1$ colors?
This post is an attempt to generalize this problem.
 A: The triangular prism graph is a counterexample.
By Brooks' theorem, the triangular prism graph $G$ has $\chi(G)=3$. However, no matter which vertex $v$ is left for last in the ordering, there is a proper coloring of $G-v$ that gives $v$'s three neighbors different colors, leaving no color for $v$. (And no matter how the vertices before $v$ are ordered, that proper coloring of $G-v$ is one of the possible outcomes of coloring them.)
Since $G$ is vertex-transitive, it's enough to demonstrate this for one choice of $v$, which I've done below:


For a counterexample if $\chi(G)+1$ colors are available, consider the circulant graph below, with $9$ vertices arranged in a circle, and edges between vertices $1$ or $2$ steps apart.
This has chromatic number $3$ (by a mod $3$ coloring around the circle). However, if $4$ colors are available, then it's possible to color the first $8$ vertices (no matter which $8$ vertices they are) so that all $4$ colors are used on the neighbors of the last vertex.
Again, since the graph is vertex-transitive, it's enough to demonstrate this for one choice of last vertex, which I've done below:


One final note: this problem is not really equivalent to the $2$-player game in the linked question about planar graphs.
In the $2$-player game, the sequence is not specified in advance: player A can look at the first few colors chosen by player B, and then decide which vertex to ask player B to color next. This makes the game easier for player A (and harder for player B).
If the sequence had to be specified in advance, player A would lose on some planar graphs, even with $5$ colors available. For example, here is a proof in the same style as above for the icosahedral graph:

However, all planar graphs have a sequence which guarantees a $6$-coloring, by putting the vertices in an order such that each vertex has at most $5$ predecessors.
