3-colorable subclasses OF P8-FREE GRAPHS

Maria Chudnovsky, Juraj Stacho

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


In this paper, we study 3-colorable graphs having no induced 8-vertex path and no induced cycles of specific lengths. We prove a characterization by critical graphs in three particular cases.

Original languageEnglish (US)
Pages (from-to)1111-1138
Number of pages28
JournalSIAM Journal on Discrete Mathematics
Issue number2
StatePublished - 2018

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


  • Coloring
  • Forbidden induced subgraphs
  • Induced paths

Fingerprint Dive into the research topics of '3-colorable subclasses OF P<sub>8</sub>-FREE GRAPHS<sup>∗</sup>'. Together they form a unique fingerprint.

Cite this