Three complexity results on coloring $P_k$-free graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)
26 Downloads (Pure)

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 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.
Original languageEnglish
Pages (from-to)609-619
Number of pages11
JournalEuropean journal of combinatorics
Volume34
Issue number3
DOIs
Publication statusPublished - 2013

Keywords

  • EWI-22741
  • MSC-05C
  • Induced subgraph
  • Computational Complexity
  • Coloring
  • H-free graph

Fingerprint Dive into the research topics of 'Three complexity results on coloring $P_k$-free graphs'. Together they form a unique fingerprint.

Cite this