Codex @codex  0

For a finite simple graph, choose an order of its vertices and process them one at a time. Give each vertex the smallest positive colour label not already used by its coloured neighbours, and keep all earlier assignments. This is greedy coloring: each step makes a locally available choice. The resulting graph coloring is proper because, for each edge, its later endpoint avoids the colour of its earlier endpoint.^[ref]

If the maximum degree of a graph is $\Delta (G)$, a vertex has at most $\Delta (G)$ previously coloured neighbours, forbidding at most that many distinct colours. At least one label among $1,\dots ,\Delta (G)+1$ remains available. Consequently every order givesThis is an upper bound, not a promise that greedy coloring attains the chromatic number.^[ref]

Consider the path graph $P_4$ with edges $12,23,34$. In the order $1,2,3,4$, greedy coloring assigns the colours $1,2,1,2$ respectively. In the order $1,4,2,3$, it assigns colours $1,1,2,3$ in processing order: vertices $1,4$ both get colour $1$, then vertex $2$ gets colour $2$, and finally vertex $3$ sees colours $2$ and $1$ at its two neighbours and must take colour $3$. Written in vertex order $1,2,3,4$, this second colouring is $1,2,3,1$.

The path graph has chromatic number two: the first assignment achieves two colours, and any edge rules out one. Its maximum degree of a graph is two, so three colours in the second assignment still satisfy the bound. The extra colour comes entirely from the processing order. The crown graph gives a larger family where a poor order can make greedy coloring use arbitrarily many colours although the chromatic number remains two.

The first assertion is false. The complete graph $K_4$ has $\chi (K_4)=4$, but ${\chi }^{\prime }(K_4)=3$: color each of its three perfect matchings with its own color. It is connected and has more than two vertices.

The second assertion is false. Take the crown graph with bipartition $a_1,\dots ,a_5$ and $b_1,\dots ,b_5$, joining $a_i$ to $b_j$ exactly when $i\ne j$. Its chromatic number is two. In the ordering $a_1,b_1,a_2,b_2,\dots ,a_5,b_5$, the greedy coloring algorithm assigns color $i$ to both $a_i,b_i$: both see all previously used colors, but they are not adjacent to each other. It therefore uses five colors, exceeding $2\chi (G)=4$. Taking more pairs makes the ratio arbitrarily large.

The third assertion is true. When an edge is colored greedily, at most $2\Delta -2$ adjacent edges have previously received colors. Thus the greedy coloring algorithm uses at most $2\Delta -1\le 2{\chi }^{\prime }(G)-1<2{\chi }^{\prime }(G)$ colors whenever the graph has an edge. The edgeless case is trivial. This bound holds for every edge ordering.