Golovach, P.A. and Paulusma, Daniel and Song, J. (2012) '4-Coloring H-free graphs when H is small.', in Theory and practice of computer science : 38th Conference on Current trends in theory and practice of computer science, SOFSEM 2012, Špindlerův Mlýn, Czech Republic, 21-27 January 2012 ; proceedings. Berlin ; Heidelberg: Springer, pp. 289-300. Lecture notes in computer science. (7147).
The k-Coloring problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed graph H on at most 6 vertices, it is known that 3-Coloring is polynomial-time solvable on H-free graphs whenever H is a linear forest and NP-complete otherwise. By solving the missing case P2 + P3, we prove the same result for 4-Coloring provided that H is a fixed graph on at most 5 vertices.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-27660-6_24|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2012|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|