Show simple item record

Defective Coloring on Classes of Perfect Graphs

hal.structure.identifierautre
dc.contributor.authorBelmonte, Rémy
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887
hal.structure.identifierLaboratoire d'InfoRmatique en Image et Systèmes d'information [LIRIS]
dc.contributor.authorMitsou, Valia
dc.date.accessioned2019-06-26T09:52:56Z
dc.date.available2019-06-26T09:52:56Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19040
dc.descriptionLNCS n°10520en
dc.language.isoenen
dc.subjectDefective coloringen
dc.subject.ddc005en
dc.titleDefective Coloring on Classes of Perfect Graphsen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages113-126en
dc.relation.ispartoftitleGraph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Revised Selected Papersen
dc.relation.ispartofeditorBodlaender, Hans L.
dc.relation.ispartofeditorWoeginger, Gerhard J.
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2017
dc.relation.ispartofpages440en
dc.relation.ispartofurl10.1007/978-3-319-68705-6en
dc.identifier.urlsitehttps://arxiv.org/abs/1702.08903v2en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-3-319-68704-9en
dc.relation.conftitle43rd International Workshop (WG 2017)en
dc.relation.confdate2017-07
dc.relation.confcityEindhovenen
dc.relation.confcountryNetherlandsen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-68705-6_9en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-31T15:13:00Z
hal.identifierhal-02165868*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record