Deciding k-colorability of P5-free graphs in polynomial time
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-4617Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-008-9197-8
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|
|Number of Pages:||8|
|Page Range:||pp. 74-81|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)