Grundy number

All other connected graphs contain either a triangle or a four-vertex path, which cause the Grundy number to be at least three.

[3] For a graph with n vertices and degeneracy d, the Grundy number is O(d log n).

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.

[7] 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.[8] There is an exact exponential time algorithm for the Grundy number that runs in time O(2.443n).

[9] 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 treewidth and the Grundy number,[11] although (assuming the exponential time hypothesis) the dependence on treewidth must be greater than singly exponential.

[9][12][13] However, on general graphs the problem is W[1]-hard when parameterized by the Grundy number.