 | ||
In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be 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).
Contents
Example
For example, for a path graph with four vertices, the chromatic number is two but the Grundy number is three: if the two endpoints of the path are colored first, the greedy coloring algorithm will use three colors for the whole graph.
Atoms
Zaker (2006) defines a sequence of graphs called t-atoms, with the property that a graph has Grundy number at least t if and only if it contains a t-atom. Each t-atom is formed from an independent set and a (t − 1)-atom, by adding one edge from each vertex of the (t − 1)-atom to a vertex of the independent set, in such a way that each member of the independent set has at least one edge incident to it. A Grundy coloring of a t-atom can be obtained by coloring the independent set first with the smallest-numbered color, and then coloring the remaining (t − 1)-atom with an additional t − 1 colors. For instance, the only 1-atom is a single vertex, and the only 2-atom is a single edge, but there are two possible 3-atoms: a triangle and a four-vertex path.
In sparse graphs
For a graph with n vertices and degeneracy d, the Grundy number is O(d log n). In particular, for graphs of bounded degeneracy (such as planar graphs) or graphs for which the chromatic number and degeneracy are bounded within constant factors of each other (such as chordal graphs) the Grundy number and chromatic number are within a logarithmic factor of each other. For interval graphs, the chromatic number and Grundy number are within a factor of 8 of each other.
Computational complexity
Testing whether the Grundy number of a given graph is at least k, for a fixed constant k, can be performed in polynomial time, by searching for all possible k-atoms that might be subgraphs of the given graph. However, this algorithm is not fixed-parameter tractable, because the exponent in its running time depends on k. When k is an input variable rather than a parameter, the problem is NP-complete. The Grundy number is at most one plus the maximum degree of the graph, and it remains NP-complete to test whether it equals one plus the maximum degree. There exists a constant c > 1 such that it is NP-hard under randomized reductions to approximate the Grundy number to within an approximation ratio better than c.
There is an exact exponential time algorithm for the Grundy number that runs in time O(2.443n).
For trees, and graphs of bounded treewidth, the Grundy number may be unboundedly large. Nevertheless, the Grundy number can be computed in polynomial time for trees, and is fixed-parameter tractable when parameterized by both the treewidth and the Grundy number, although (assuming the exponential time hypothesis) the dependence on treewidth must be greater than singly exponential. When parameterized by the Grundy number itself, it can be computed in fixed-parameter tractable time for chordal graphs and claw-free graphs, and also (using general results on subgraph isomorphism in sparse graphs to search for atoms) for graphs of bounded expansion.
Well-colored graphs
A graph is called well-colored if its Grundy number equals its chromatic number. Testing whether a graph is well-colored is coNP-complete. The hereditarily well-colored graphs (graphs for which every induced subgraph is well-colored) are exactly the cographs, the graphs that do not have a four-vertex path as an induced subgraph.