Grundy number
In
Examples
The
The complete bipartite graphs are the only connected graphs whose Grundy number is two. All other connected graphs contain either a triangle or a four-vertex path, which cause the Grundy number to be at least three.[3]
The crown graphs are obtained from complete bipartite graphs by removing a perfect matching. As a result, for each vertex on one side of the bipartition, there is exactly one vertex on the opposite side of the bipartition that it is not adjacent to. As bipartite graphs, they can be colored with two colors, but their Grundy number is : if a greedy coloring algorithm considers each matched pair of vertices in order, each pair will receive a different color. As this example shows, the Grundy number can be larger than the chromatic number by a factor linear in the number of graph vertices.[4]
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.[3]
In sparse graphs
For a graph with n vertices and
Computational complexity
Testing whether the Grundy number of a given graph is at least k, for a fixed constant k, can be performed in
There is an exact
For trees, and graphs of bounded treewidth, the Grundy number may be unboundedly large.[10] Nevertheless, the Grundy number can be computed in polynomial time for trees, and is fixed-parameter tractable when parameterized by both the
However, on general graphs the problem is W[1]-hard when parameterized by the Grundy number. [14]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.[3] 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.[2]
References
- MR 2019200.
- ^ MR 0539075.
- ^ MR 2273147.
- )
- S2CID 181800.
- S2CID 207223738.
- MR 2770795.
- ^ Kortsarz, Guy (2007), "A lower bound for approximating Grundy numbering", Discrete Mathematics & Theoretical Computer Science, 9 (1).
- ^ S2CID 5514223.
- S2CID 8839035.
- MR 1477655.
- MR 3024787.
- MR 2920058.
- S2CID 250614665.