Greedy coloring

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.

Let $x$ have two nonadjacent neighbours $y,z$ in a finite graph $G$, with $G-\{y,z\}$ connected. Then $\chi (G)\le \Delta (G)$. Give $y,z$ one common colour. In a spanning tree of the remaining graph rooted at $x$, order vertices from larger to smaller distance from the root and colour greedily in that order. Every vertex before $x$ has an uncoloured parent, so at most $\Delta (G)-1$ colours are forbidden there. At $x$, the two initial neighbours use the same colour, so again at most $\Delta (G)-1$ distinct colours are forbidden. This constructs a proper colouring from a palette of $\Delta (G)$ colours. It is a useful local step in Brooks' theorem.

In a proper partial graph coloring, let $R_v$ count coloured neighbours and $D_v$ count their distinct colours. The saving $S_v=R_v-D_v$ leaves $K-D_v$ available colours for only $d(v)-R_v$ initially uncoloured neighbours. If the displayed inequality holds at every vertex, ordinary greedy completion succeeds. Each additionally coloured neighbour removes at most one available colour while also reducing the number of uncoloured neighbours by one.

The number of coloured neighbours of $v$ minus the number of distinct colours on those neighbours. Repeated colours among pairwise nonadjacent neighbours reduce the number of unavailable colours without increasing the number of neighbours still to colour.