Show simple item record

dc.contributor.authorLozin, Vadim
dc.contributor.authorRaman, Rajiv
dc.contributor.authorRies, Bernard
dc.contributor.authorDabrowski, Konrad
dc.date.accessioned2011-03-23T15:27:02Z
dc.date.available2011-03-23T15:27:02Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5807
dc.language.isoenen
dc.subjectVertex colouringen
dc.subjectTriangle-free graphsen
dc.subjectPolynomial-time algorithmen
dc.subjectClique-widthen
dc.subject.ddc511
dc.titleColouring vertices of triangle-free graphsen
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherDIMAP, University of Warwick;Royaume-Uni
dc.description.abstractenThe vertex colouring problem is known to be NP-comple-te in the class of triangle-free graphs. Moreover, it remains NP-complete even if we additionally exclude a graph F which is not a forest. We study the computational complexity of the problem in (K3,F)-free graphs with F being a forest. From known results it follows that for any forest F on 5 vertices the vertex colouring problem is polynomial-time solvable in the class of (K3,F)-free graphs. In the present paper, we show that the problem is also polynomial-time solvable in many classes of (K3,F)-free graphs with F being a forest on 6 vertices.en
dc.identifier.citationpages184-195
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber6410
dc.relation.ispartoftitleGraph Theoretic Concepts in Computer Science 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers
dc.relation.ispartofeditorThilikos, Dimitrios M.
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin
dc.relation.ispartofdate2010
dc.relation.ispartofpages338
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-16926-7
dc.description.sponsorshipprivateouien
dc.subject.ddclabelPrincipes généraux des mathématiques
dc.relation.ispartofisbn978-3-642-16925-0
dc.relation.conftitleGraph Theoretic Concepts in Computer Science 36th International Workshopen
dc.relation.confdate2010-06
dc.relation.confcityZarosen
dc.relation.confcountryGrèceen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-16926-7_18


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