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
TypeCommunication / Conférence
External document linkhttps://arxiv.org/abs/1702.08903v2
Conference title43rd International Workshop (WG 2017)
Book titleGraph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Revised Selected Papers
Book authorBodlaender, Hans L.; Woeginger, Gerhard J.
Number of pages440
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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 / KeywordsDefective coloring
Showing items related by title and author.