| dc.contributor.author | Lozin, Vadim | |
| dc.contributor.author | Raman, Rajiv | |
| dc.contributor.author | Ries, Bernard | |
| dc.contributor.author | Dabrowski, Konrad | |
| dc.date.accessioned | 2011-03-23T15:27:02Z | |
| dc.date.available | 2011-03-23T15:27:02Z | |
| dc.date.issued | 2010 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/5807 | |
| dc.language.iso | en | en |
| dc.subject | Vertex colouring | en |
| dc.subject | Triangle-free graphs | en |
| dc.subject | Polynomial-time algorithm | en |
| dc.subject | Clique-width | en |
| dc.subject.ddc | 511 | |
| dc.title | Colouring vertices of triangle-free graphs | en |
| dc.type | Communication / Conférence | |
| dc.contributor.editoruniversityother | DIMAP, University of Warwick;Royaume-Uni | |
| dc.description.abstracten | The 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.citationpages | 184-195 | |
| dc.relation.ispartofseriestitle | Lecture Notes in Computer Science | |
| dc.relation.ispartofseriesnumber | 6410 | |
| dc.relation.ispartoftitle | Graph Theoretic Concepts in Computer Science
36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers | |
| dc.relation.ispartofeditor | Thilikos, Dimitrios M. | |
| dc.relation.ispartofpublname | Springer | |
| dc.relation.ispartofpublcity | Berlin | |
| dc.relation.ispartofdate | 2010 | |
| dc.relation.ispartofpages | 338 | |
| dc.relation.ispartofurl | http://dx.doi.org/10.1007/978-3-642-16926-7 | |
| dc.description.sponsorshipprivate | oui | en |
| dc.subject.ddclabel | Principes généraux des mathématiques | |
| dc.relation.ispartofisbn | 978-3-642-16925-0 | |
| dc.relation.conftitle | Graph Theoretic Concepts in Computer Science 36th International Workshop | en |
| dc.relation.confdate | 2010-06 | |
| dc.relation.confcity | Zaros | en |
| dc.relation.confcountry | Grèce | en |
| dc.identifier.doi | http://dx.doi.org/10.1007/978-3-642-16926-7_18 | |
