3-colorable subclasses OF P8-FREE GRAPHS

Maria Chudnovsky, Juraj Stacho

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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
Volume32
Issue number2
DOIs
StatePublished - Jan 1 2018

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • 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