• 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

Grundy Coloring & Friends, Half-Graphs, Bicliques

Aboulker, Pierre; Bonnet, Edouard; Kim, Eun Jung; Sikora, Florian (2020), Grundy Coloring & Friends, Half-Graphs, Bicliques, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 58:1-58:18. 10.4230/LIPIcs.STACS.2020.58

Type
Communication / Conférence
External document link
https://dx.doi.org/10.4230/LIPIcs.STACS.2020.58
Date
2020
Conference title
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Conference date
2020-03
Conference country
FRANCE
Book title
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISBN
978-3-95977-140-5
Pages
58:1-58:18
Publication identifier
10.4230/LIPIcs.STACS.2020.58
Metadata
Show full item record
Author(s)
Aboulker, Pierre
Bonnet, Edouard cc
Kim, Eun Jung
Sikora, Florian cc
Abstract (EN)
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order σ, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering σ, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A brute-force f(k)n^{2^{k-1}}-time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on K_{t,t}-free graphs for b-Chromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.

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 (2015) Communication / Conférence
  • 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
    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