The Library
Colouring vertices of triangle-free graphs
Tools
Dabrowski, Konrad, Lozin, Vadim V., Raman, Rajiv and Ries, Bernard (2010) Colouring vertices of triangle-free graphs. In: 36th International Workshop on Graph-Theoretic Concepts in Computer Science, Zaros, Greece, 28-30 Jun 2010. Published in: Lecture Notes in Computer Science, Volume 6410 pp. 184-195. doi:10.1007/978-3-642-16926-7_18 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The VERTEX COLOURING problem is known to be NP-complete 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 (K(3), 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.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Graph coloring | ||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
ISSN: | 0302-9743 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Volume 6410 | ||||
Page Range: | pp. 184-195 | ||||
DOI: | 10.1007/978-3-642-16926-7_18 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Description: | From: Graph-theoretic concepts in computer science : 36th international workshop, WG 2010, Zarãaos, Crete, Greece, June 28-30, 2010 : revised papers |
||||
Funder: | University of Warwick. Centre for Discrete Mathematics and Its Applications | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 36th International Workshop on Graph-Theoretic Concepts in Computer Science | ||||
Type of Event: | Conference | ||||
Location of Event: | Zaros, Greece | ||||
Date(s) of Event: | 28-30 Jun 2010 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |