• 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

Defective Coloring on Classes of Perfect Graphs

Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2017), Defective Coloring on Classes of Perfect Graphs, in Bodlaender, Hans L.; Woeginger, Gerhard J., Graph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Revised Selected Papers, Springer International Publishing : Cham, p. 113-126. 10.1007/978-3-319-68705-6_9

Type
Communication / Conférence
External document link
https://arxiv.org/abs/1702.08903v2
Date
2017
Conference title
43rd International Workshop (WG 2017)
Conference date
2017-07
Conference city
Eindhoven
Conference country
Netherlands
Book title
Graph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Revised Selected Papers
Book author
Bodlaender, Hans L.; Woeginger, Gerhard J.
Publisher
Springer International Publishing
Published in
Cham
ISBN
978-3-319-68704-9
Number of pages
440
Pages
113-126
Publication identifier
10.1007/978-3-319-68705-6_9
Metadata
Show full item record
Author(s)
Belmonte, Rémy
autre
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mitsou, Valia
Laboratoire d'InfoRmatique en Image et Systèmes d'information [LIRIS]
Abstract (EN)
In Defective Coloring we are given a graph G and two integers χd,Δ∗ and are asked if we can χd -color G so that the maximum degree induced by any color class is at most Δ∗ . We show that this natural generalization of Coloring is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters χd,Δ∗ is set to the smallest possible fixed value that does not trivialize the problem ( χd=2 or Δ∗=1 ). Together with a simple treewidth-based DP algorithm this completely determines the complexity of the problem also on chordal graphs.We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that Defective Coloring is in P for cographs if either χd or Δ∗ is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both χd and Δ∗ are unbounded.
Subjects / Keywords
Defective coloring

Related items

Showing items related by title and author.

  • Thumbnail
    Defective Coloring on Classes of Perfect Graphs 
    Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2022) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized (Approximate) Defective Coloring 
    Belmonte, Rémy; Lampis, Michael; Mitsou, Valia (2020) Article accepté pour publication ou publié
  • Thumbnail
    Token Sliding on Split Graphs 
    Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian (2019) Communication / Conférence
  • Thumbnail
    Token Sliding on Split Graphs 
    Sikora, Florian; Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) Article accepté pour publication ou publié
  • Thumbnail
    Grundy Distinguishes Treewidth from Pathwidth 
    Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota (2020) 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