Show simple item record

hal.structure.identifierDepartment of Mathematics [Bergen] [UiB]
dc.contributor.authorGolovach, Petr A.*
hal.structure.identifierSchool of Engineering and Computing Sciences
dc.contributor.authorPaulusma, Daniël*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorRies, Bernard*
dc.date.accessioned2013-09-12T10:11:57Z
dc.date.available2013-09-12T10:11:57Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11643
dc.language.isoenen
dc.subjectgraphsen
dc.subjectColoring problemen
dc.subject.ddc006.3en
dc.titleColoring Graphs Characterized by a Forbidden Subgraphen
dc.typeCommunication / Conférence
dc.description.abstractenThe Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H. A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly H-free and initiate a complexity classification of Coloring for strongly H-free graphs. We show that Coloring is NP-complete for strongly H-free graphs, even for k = 3, when H contains a cycle, has maximum degree at least five, or contains a connected component with two vertices of degree four. We also give three conditions on a forest H of maximum degree at most four and with at most one vertex of degree four in each of its connected components, such that Coloring is NP-complete for strongly H-free graphs even for k = 3. Finally, we classify the computational complexity of Coloring on strongly H-free graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H is a forest that has at most seven vertices and maximum degree at most four.en
dc.identifier.citationpages443-454en
dc.relation.ispartofseriestitleLecture Notes in Computer Scienceen
dc.relation.ispartofseriesnumber7464en
dc.relation.ispartoftitleMathematical Foundations of Computer Science 2012 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012, Proceedingsen
dc.relation.ispartofeditorRovan, Branislav
dc.relation.ispartofeditorSassone, Vladimiro
dc.relation.ispartofeditorWidmayer, Peter
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2012
dc.relation.ispartofpages825en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-32589-2en
dc.subject.ddclabelIntelligence artificielleen
dc.relation.ispartofisbn978-3-642-32588-5en
dc.relation.conftitle37th International Symposium on Mathematical Foundations of Computer Science 2012, MFCS 2012en
dc.relation.confdate2012-08
dc.relation.confcityBratislavaen
dc.relation.confcountrySlovakiaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-642-32589-2_40en
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01509549*
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