Grundy number

An optimal greedy coloring (left) and Grundy coloring (right) of a crown graph. The numbers indicate the order in which the greedy algorithm colors the vertices.

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the largest number of colors in any greedy coloring of the graph. More precisely, it is the number of colors used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).