Three Complexity Results on Coloring $P_k$-Free Graphs

Haitze J. Broersma, Fedor V. Fomin, Petr A. Golovach, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)


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.
Original languageUndefined
Title of host publicationCombinatioral Algorithms - Proceedings of the 20th International Workshop , IWOCA 2009
EditorsJiri Fiala, Jan Kratochvil, Mirka Miller
Place of PublicationBerlin
Number of pages10
ISBN (Print)978-3-642-10216-5
Publication statusPublished - 2009
Event20th International Workshop on Combinatioral Algorithms, IWOCA 2009 - Hradec nad Moravicí, Czech Republic, Hradec nad Moravicí, Czech Republic
Duration: 28 Jun 20092 Jul 2009
Conference number: 20

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Workshop on Combinatioral Algorithms, IWOCA 2009
Abbreviated titleIWOCA 2009
Country/TerritoryCzech Republic
CityHradec nad Moravicí
Other28 June - 2 July 2009


  • METIS-266491
  • IR-71249
  • EWI-17840
  • Computational Complexity
  • Pk-free graph
  • Graph coloring

Cite this