Graph coloring
Greedy coloring

The greedy algorithm considers the vertices in a specific order v 1 {\displaystyle v_{1}},…, v n {\displaystyle v_{n}} and assigns to v i {\displaystyle v_{i}} the smallest available color not used by v i {\displaystyle v_{i}} 's neighbours among v 1 {\displaystyle v_{1}},…, v i − 1 {\displaystyle v_{i-1}}, adding a fresh color if needed. The quality of the resulting coloring depends on the chosen ordering. There exists an ordering that leads to a greedy coloring with the optimal number of χ (G) {\displaystyle \chi (G)} colors. On the other hand, greedy colorings can be arbitrarily bad; for example, the crown graph on n vertices can be 2-colored, but has an ordering that leads to a greedy coloring with n / 2 {\displaystyle n/2} colors.

For chordal graphs, and for special cases of chordal graphs such as interval graphs and indifference graphs, the greedy coloring algorithm can be used to find optimal colorings in polynomial time, by choosing the vertex ordering to be the reverse of a perfect elimination ordering for the graph. The perfectly orderable graphs generalize this property, but it is NP-hard to find a perfect ordering of these graphs.

If the vertices are ordered according to their degrees, the resulting greedy coloring uses at most max i min { d (x i) + 1, i } {\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}} colors, at most one more than the graph's maximum degree. This heuristic is sometimes called the Welsh–Powell algorithm. Another heuristic due to Brélaz establishes the ordering dynamically while the algorithm proceeds, choosing next the vertex adjacent to the largest number of different colors. Many other graph coloring heuristics are similarly based on greedy coloring for a specific static or dynamic strategy of ordering the vertices, these algorithms are sometimes called sequential coloring algorithms.

The maximum (worst) number of colors that can be obtained by the greedy algorithm, by using a vertex ordering chosen to maximize this number, is called the Grundy number of a graph.
detectable_content:postscript