4-Coloring P6-Free Graphs with No Induced 5-Cycles

Maria Chudnovsky, Peter Maceli, Juraj Stacho, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C5 and no induced 6-vertex path P6.

Original languageEnglish (US)
Pages (from-to)262-285
Number of pages24
JournalJournal of Graph Theory
Issue number3
StatePublished - Mar 1 2017

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


  • algorithm
  • coloring
  • induced subgraphs
  • path


Dive into the research topics of '4-Coloring P6-Free Graphs with No Induced 5-Cycles'. Together they form a unique fingerprint.

Cite this