Show simple item record

dc.contributor.authorPaulusma, Daniël
dc.contributor.authorPicouleau, Christophe
dc.contributor.authorRies, Bernard
dc.date.accessioned2020-05-22T14:34:57Z
dc.date.available2020-05-22T14:34:57Z
dc.date.issued2019
dc.identifier.issn0166-218X
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20769
dc.language.isoenen
dc.subjectvertex deletionen
dc.subjectedge contractionen
dc.subjectchromatic numberen
dc.subject.ddc511en
dc.titleCritical vertices and edges in H-free graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both problems restricted to H-free graphs, that is, graphs with no induced subgraph isomorphic to H. Moreover, we show that an edge is critical if and only if its contraction reduces the chromatic number by one. Hence, we also obtain a complexity dichotomy for the problem of deciding if a graph has an edge whose contraction reduces the chromatic number by one.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol257en
dc.relation.isversionofjnldate2019-03
dc.relation.isversionofjnlpages361-367en
dc.relation.isversionofdoi10.1016/j.dam.2018.08.016en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-05-22T14:32:48Z
hal.person.labIds
hal.person.labIds
hal.person.labIds989


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record