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

Maria Chudnovsky, Peter Maceli, Juraj Stacho, Mingxian Zhong

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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
Volume84
Issue number3
DOIs
StatePublished - Mar 1 2017

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • algorithm
  • coloring
  • induced subgraphs
  • path

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

  • Cite this