The complexity of coloring graphs without long induced paths

Jirí Sgall, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

46 Citations (Scopus)
24 Downloads (Pure)

Abstract

We discuss the computational complexity of determining the chromatic number of graphs without long induced paths. We prove NP-completeness of deciding whether a Ps-free graph is 5-colorable and of deciding whether a Pi2-free graph is 4-colorable. Moreover, we give a polynomial time algorithm for deciding whether a Ps-free graph is 3-colorable.
Original languageEnglish
Pages (from-to)107-117
Number of pages11
JournalActa cybernetica
Volume15
Issue number1
Publication statusPublished - 2001

Keywords

  • METIS-202635

Fingerprint Dive into the research topics of 'The complexity of coloring graphs without long induced paths'. Together they form a unique fingerprint.

Cite this