Show simple item record

Critical vertices and edges in H-free graphs

hal.structure.identifier
dc.contributor.authorPaulusma, Daniël
hal.structure.identifier
dc.contributor.authorPicouleau, Christophe
HAL ID: 181059
ORCID: 0000-0001-8092-1923
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
26280.pdf
Size:
393.8Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record