= Greedy coloring
{wiki}
= Greedy graph coloring
{synonym}
= Greedy colouring
{synonym}
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.https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/1ccaf180bcd244fddd32e60789fa922f_h9wxtqoa1jY.pdf[Leighton, MIT Graph Theory and Coloring, transcript pages 12–13]{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,\ldots,\Delta(G)+1$ remains available. Consequently every order gives
$$
\chi(G)\leq\text{number of colours used by greedy colouring}\leq\Delta(G)+1.
$$
This is an upper bound, not a promise that <greedy coloring> attains the <chromatic number>.https://ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1200j_s24_lec11.pdf[MIT, Graphs and Coloring, Theorem 2]{ref}
\Image[/greedy-coloring-order.png]
{title=Two orders for <greedy coloring> of the same <path graph> $P_4$}
{description=The <edges> are $12,23,34$ in both drawings. Each dot shows its assigned colour number, with the <vertex> label above and its processing step below. The order $1,2,3,4$ uses two colours; the order $1,4,2,3$ uses three.}
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.
Back to article page
