Complexity of Grundy coloring and its variants

2014/07/20 by Edouard Bonnet, Florent Foucaud, Bonnet, Edouard +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO

paper · pdf · doi:10.48550/arxiv.1407.5336

24 pages, 7 figures. This version contains some new results and improvements. A short paper based on version v2 appeared in COCOON'15

arxiv created 2015/10/30 · arxiv updated 2015/11/03

Abstract

The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least k. We also study the variants WEAK GRUNDY COLORING (where the coloring is not necessarily proper) and CONNECTED GRUNDY COLORING (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that GRUNDY COLORING can be solved in time O^*(2.443ⁿ) and WEAK GRUNDY COLORING in time O^*(2.716ⁿ) on graphs of order n. While GRUNDY COLORING and WEAK GRUNDY COLORING are known to be solvable in time O^*(2^O(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^*(2^{o(wlog w)}). We also describe an O^*(2^2^O(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.

Related

• Grundy Coloring & friends, Half-Graphs, Bicliques
• O(VE) time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth
• Parameterized Saga of First-Fit and Last-Fit Coloring
• Grundy Packing Coloring of Graphs
• Spectral upper bounds for the Grundy number of a graph