• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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érence
External document link
http://arxiv.org/abs/1407.5336v3
Date
2015
Conference title
21st International Conference on Computing and Combinatorics, COCOON 2015
Conference date
2015-08
Conference city
Beijing
Conference country
China
Book title
Computing and Combinatorics. 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings
Book author
Xu, Dachuan; Du, Donglei; Du, Ding-Zhu
Publisher
Springer International Publishing
ISBN
978-3-319-21397-2
Pages
109-120
Publication identifier
10.1007/978-3-319-21398-9_9
Metadata
Show full item record
Author(s)
Bonnet, Édouard cc
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 cc
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
Complexity

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity of Grundy coloring and its variants 
    Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2018) Article accepté pour publication ou publié
  • Thumbnail
    Grundy Coloring & Friends, Half-Graphs, Bicliques 
    Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2020) Communication / Conférence
  • Thumbnail
    EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs 
    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é
  • Thumbnail
    QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs 
    Bonnet, Édouard; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, Pawel; Sikora, Florian (2018) Communication / Conférence
  • Thumbnail
    Twin-width III: Max Independent Set, Min Dominating Set, and Coloring 
    Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo