The Library
Vertex coloring of graphs with few obstructions
Tools
Lozin, Vadim V. and Malyshev, D. S. (2017) Vertex coloring of graphs with few obstructions. Discrete Applied Mathematics, 216 . pp. 273-280. doi:10.1016/j.dam.2015.02.015 ISSN 0166-218X.
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.1016/j.dam.2015.02.015
Abstract
We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||||
Publisher: | Elsevier Science Ltd. | ||||||
ISSN: | 0166-218X | ||||||
Official Date: | 10 January 2017 | ||||||
Dates: |
|
||||||
Volume: | 216 | ||||||
Page Range: | pp. 273-280 | ||||||
DOI: | 10.1016/j.dam.2015.02.015 | ||||||
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 |