Greedy coloring in descending degree ordering is not always optimal

Question

Finding the optimal ordering for Greedy coloring is NP-hard, and it seems like ordering the vertices in descending degree is always a good choice (according to Wikipedia). I've tried by hand for a couple of examples and it produced an optimal coloring every time. Does anyone know a counter-example?

Answer 1

Take any example of a graph with a bad ordering of vertices, such that the greedy coloring is not optimal. By adding leaves in a suitable way, you can make that bad ordering a descending degree ordering, without changing the chromatic number.

For a concrete example, take the graph with vertices $v_1$, $v_2$, $v_3$, $v_4$ and edges $v_1v_4$, $v_4v_3$, $v_3v_2$. The chromatic number is $2$, but the greedy coloring in the order $v_1,v_2,v_3,v_4$ uses three colors. Of course this is not a descending degree ordering.

Now add vertices $w_1$, $x_1$, $y_1$, $z_1$, $w_2$, $x_2$, $y_2$, $w_3$ and edges $v_1w_1$, $v_1x_1$, $v_1y_1$, $v_1z_1$, $v_2w_2$, $v_2x_2$, $v_2y_2$, $v_3w_3$. This is the example you want: the chromatic number is still $2$, and a descending degree ordering starts $v_1,v_2,v_3,v_4$ and still uses three colors.