Show simple item record

dc.contributor.authorRies, Bernard*
dc.contributor.authorRaman, Rajiv*
dc.contributor.authorLozin, Vadim*
dc.contributor.authorDabrowski, Konrad*
dc.date.accessioned2012-02-17T10:11:34Z
dc.date.available2012-02-17T10:11:34Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/8185
dc.language.isoenen
dc.subjectClique-widthen
dc.subjectPolynomial-time algorithmen
dc.subjectTriangle-free graphsen
dc.subjectVertex colouringen
dc.subject.ddc511en
dc.titleColouring vertices of triangle-free graphs without forestsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDIMAP & Mathematics Institute, University of Warwick;Royaume-Uni
dc.description.abstractenThe vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of triangle-free graphs obtained by forbidding graphs without cycles, i.e., forests, and prove polynomial-time solvability of the problem in many classes of this type. In particular, our paper, combined with some previously known results, provides a complete description of the complexity status of the problem in subclasses of triangle-free graphs obtained by forbidding a forest with at most 6 vertices.en
dc.relation.isversionofjnlnameDiscrete Mathematics
dc.relation.isversionofjnlvol312en
dc.relation.isversionofjnlissue7en
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages1372-1385en
dc.relation.isversionofdoi10.1016/j.disc.2011.12.012en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.person.labIds989*
hal.person.labIds*
hal.person.labIds*
hal.person.labIds*
hal.identifierhal-01509679*


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