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.
Restricted to UT campus only: Request a copy
|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 pre-coloring extension version of 5-coloring remains NP-complete 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 pre-coloring extension version of 3-coloring is polynomially solvable for -free graphs. This implies a simpler algorithm for checking the 3-colorability of -free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for -free graphs. This problem was known to be polynomially solvable for -free graphs and NP-complete for -free graphs, so there remains one open case.
|Item Type:||Conference or Workshop Item|
|Copyright:||© 2009 Springer|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/71249|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page