Three complexity results on coloring free graphs
Broersma, Hajo and Fomin, Fedor V. and Golovach, Petr A. and Paulusma, Daniël (2009) Three complexity results on coloring free graphs. In: 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, June 28  July 2 2009, Hradec nad Moravicí, Czech Republic (pp. pp. 95104).
PDF
Restricted to UT campus only : Request a copy 216kB 
Abstract:  We prove three complexity results on vertex coloring problems restricted to free graphs, i.e., graphs that do not contain a path on vertices as an induced subgraph. First of all, we show that the precoloring extension version of 5coloring remains NPcomplete when restricted to ree graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on free graphs. Secondly, we show that the precoloring extension version of 3coloring is polynomially solvable for free graphs. This implies a simpler algorithm for checking the 3colorability of free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6coloring is NPcomplete for free graphs. This problem was known to be polynomially solvable for free graphs and NPcomplete for 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/9783642102172_12 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page