The Library
Coloring vertices of claw-free graphs in three colors
Tools
Lozin, Vadim V. and Purcell, Christopher (2014) Coloring vertices of claw-free graphs in three colors. Journal of Combinatorial Optimization, Volume 28 (Number 2). pp. 462-479. doi:10.1007/s10878-012-9577-5 ISSN 1382-6905.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s10878-012-9577-5
Abstract
We study the computational complexity of the vertex 3-colorability problem in the class of claw-free graphs. Both the problem and the class received much attention in the literature, separately of each other. However, very little is known about the 3-colorability problem restricted to the class of claw-free graphs beyond the fact the problem is NP-complete under this restriction. In this paper we first strengthen this negative fact by revealing various further restrictions under which the problem remains NP-complete. Then we derive a number of positive results that deal with polynomially solvable cases of the problem in the class of claw-free graphs.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Journal of Combinatorial Optimization | ||||
Publisher: | Springer New York LLC | ||||
ISSN: | 1382-6905 | ||||
Official Date: | 1 August 2014 | ||||
Dates: |
|
||||
Volume: | Volume 28 | ||||
Number: | Number 2 | ||||
Page Range: | pp. 462-479 | ||||
DOI: | 10.1007/s10878-012-9577-5 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |