We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Three complexity results on coloring Pk-free graphs.

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:
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