Complexity of Grundy coloring and its variants

We show that Grundy Coloring can be solved in time O∗(2.443n) and Weak Grundy Coloring in time O∗(2.716n) on graphs of order n. While Grundy Coloring and Weak Grundy Coloring are known to be solvable in time O∗(2O(wk)) for graphs of treewidth w (where k is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time O∗(2o(wlogw)). We also describe an O∗(22O(k)) algorithm for Weak Grundy Coloring, which is therefore FPT for the parameter k. Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for Grundy Coloring). Although we do not know whether Grundy Coloring is in FPT, we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for Grundy Coloring and Weak Grundy Coloring on apex-minor graphs. In stark contrast with the two other problems, we show that Connected Grundy Coloring is NP-complete already for k=7 colors.