Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421184 | Discrete Applied Mathematics | 2013 | 11 Pages |
Abstract
The kk-Coloring problem is to test whether a graph can be colored with at most kk colors such that no two adjacent vertices receive the same color. If a graph GG does not contain a graph HH as an induced subgraph, then GG is called HH-free. For any fixed graph HH on at most six vertices, it is known that 33-Coloring is polynomial-time solvable on HH-free graphs whenever HH is a linear forest, and NP-complete otherwise. By solving the missing case P2+P3P2+P3, we prove the same result for 44-Coloring provided that HH is a fixed graph on at most five vertices.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Petr A. Golovach, Daniël Paulusma, Jian Song,