Broersma, H. J. and Fomin, F. V. and Golovach, P. A. and Paulusma, Daniel (2009) 'Three complexity results on coloring Pk-free graphs.', in Combinatorial algorithms : 20th InternationalWorkshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers. Berlin: Springer, pp. 95-104. Lecture notes in computer science. (5874).
We prove three complexity results on vertex coloring problems restricted to Pk-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to P6-free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on P5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P7-free graphs. This problem was known to be polynomially solvable for P5-free graphs and NP-complete for P8-free graphs, so there remains one open case.
|Item Type:||Book chapter|
|Keywords:||Graph coloring, Pk-free graph, Computational complexity.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-10217-2_12|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2009|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|