Three complexity results on coloring $P_k$-free graphs


Share/Save/Bookmark

Broersma, Hajo and Fomin, Fedor V. and Golovach, Petr A. and Paulusma, Daniël (2009) Three complexity results on coloring $P_k$-free graphs. In: 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, June 28 - July 2 2009, Hradec nad Moravicí, Czech Republic.

[img]PDF
Restricted to UT campus only
: Request a copy
211Kb
Abstract:We prove three complexity results on vertex coloring problems restricted to $P_k$-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 $P_6$-ree graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on $P_5$-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for $P_6$-free graphs. This implies a simpler algorithm for checking the 3-colorability of $P_6$-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for $P_7$-free graphs. This problem was known to be polynomially solvable for $P_5$-free graphs and NP-complete for $P_8$-free graphs, so there remains one open case.
Item Type:Conference or Workshop Item
Copyright:© 2009 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/71249
Official URL:http://dx.doi.org/10.1007/978-3-642-10217-2_12
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page