The Library
Deciding k-colorability of P5-free graphs in polynomial time
Tools
Tools
Tools
Hoang, Chinh T., Kaminski, Marcin, Lozin, Vadim V., Sawada, Joe and Shu, Xiao. (2010) Deciding k-colorability of P5-free graphs in polynomial time. Algorithmica, Vol.57 (No.1). pp. 74-81. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-008-9197-8
Abstract
The problem of computing the chromatic number of a P (5)-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P (5)-free graph admits a k-coloring, and finding one, if it does.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Mathematics |
| Journal or Publication Title: | Algorithmica |
| Publisher: | Springer Verlag |
| ISSN: | 0178-4617 |
| Date: | May 2010 |
| Volume: | Vol.57 |
| Number: | No.1 |
| Number of Pages: | 8 |
| Page Range: | pp. 74-81 |
| Identification Number: | 10.1007/s00453-008-9197-8 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Funder: | NSERC |
| URI: | http://wrap.warwick.ac.uk/id/eprint/16567 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
