Show simple item record

hal.structure.identifier
dc.contributor.authorPaulusma, Daniël*
hal.structure.identifier
dc.contributor.authorGolovach, Petr A.*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorRies, Bernard*
dc.date.accessioned2014-09-26T08:30:17Z
dc.date.available2014-09-26T08:30:17Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/13964
dc.language.isoenen
dc.subjectForbidden subgraphsen
dc.subjectGraph coloringen
dc.subjectAlgorithmsen
dc.subjectComplexityen
dc.subject.ddc006.3en
dc.titleColoring graphs characterized by a forbidden subgraphen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherSchool of Engineering and Computing Sciences, Durham University;Royaume-Uni
dc.contributor.editoruniversityotherUniversité de Bergen;Norvège
dc.description.abstractenThe Coloring problem is to test whether a given graph can be colored with at most kk colors for some given kk, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph HH as an induced subgraph is known for each fixed graph HH. A natural variant is to forbid a graph HH only as a subgraph. We call such graphs strongly HH-free and initiate a complexity classification of Coloring for strongly HH-free graphs. We show that Coloring is NP-complete for strongly HH-free graphs, even for k=3k=3, when HH contains a cycle, has maximum degree at least 5, or contains a connected component with two vertices of degree 4. We also give three conditions on a forest HH of maximum degree at most 4 and with at most one vertex of degree 4 in each of its connected components, such that Coloring is NP-complete for strongly HH-free graphs even for k=3k=3. Finally, we classify the computational complexity of Coloring on strongly HH-free graphs for all fixed graphs HH up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when HH is a forest that has at most seven vertices and maximum degree at most 4.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol180
dc.relation.isversionofjnldate2015
dc.relation.isversionofjnlpages101-110
dc.relation.isversionofdoi10.1016/j.dam.2014.08.008en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelInteligence artificielleen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01509547*
hal.version1*
hal.update.actionupdateMetadata*
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