Complexity of Grundy Coloring and Its Variants
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015), Complexity of Grundy Coloring and Its Variants, in Xu, Dachuan; Du, Donglei; Du, Ding-Zhu, Computing and Combinatorics. 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings, Springer International Publishing, p. 109-120. 10.1007/978-3-319-21398-9_9
Type
Communication / ConférenceExternal document link
http://arxiv.org/abs/1407.5336v3Date
2015Conference title
21st International Conference on Computing and Combinatorics, COCOON 2015Conference date
2015-08Conference city
BeijingConference country
ChinaBook title
Computing and Combinatorics. 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, ProceedingsBook author
Xu, Dachuan; Du, Donglei; Du, Ding-ZhuPublisher
Springer International Publishing
ISBN
978-3-319-21397-2
Pages
109-120
Publication identifier
Metadata
Show full item recordAuthor(s)
Bonnet, Édouard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Foucaud, Florent
Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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 show that Grundy Coloring can be solved in time O∗(2.443n) on graphs of order n. While the problem is known to be solvable in time f(k,w)⋅n for graphs of treewidth w, we prove that under the Exponential Time Hypothesis, it cannot be computed in time O∗(cw), for any constant c. We also study the parameterized complexity of Grundy Coloring parameterized by the number of colors, showing that it is in FPTfor graphs including chordal graphs, claw-free graphs, and graphs excluding a fixed minor.Finally, we consider two previously studied variants of Grundy Coloring, namely Weak Grundy Coloring and Connected Grundy Coloring. We show that Weak Grundy Coloring is fixed-parameter tractable with respect to the weak Grundy number. In stark contrast, it turns out that checking whether a given graph has connected Grundy number at least k is NP-complete already for k=7.Subjects / Keywords
ComplexityRelated items
Showing items related by title and author.
-
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2018) Article accepté pour publication ou publié
-
Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2023) Article accepté pour publication ou publié
-
Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2020) Communication / Conférence
-
Bonamy, Marthe; Bonnet, Edouard; Bousquet, Nicolas; Charbit, Pierre; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, P.; Sikora, Florian; Thomassé, S. (2021) Article accepté pour publication ou publié
-
Bonnet, Édouard; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, Pawel; Sikora, Florian (2018) Communication / Conférence