Coloring graphs with no induced five-vertex path or gem

Maria Chudnovsky, T. Karthick, Peter Maceli, Frédéric Maffray

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

For a graph (Formula presented.), let (Formula presented.) and (Formula presented.), respectively, denote the chromatic number and clique number of (Formula presented.). We give an explicit structural description of ((Formula presented.), gem)-free graphs, and show that every such graph (Formula presented.) satisfies (Formula presented.). Moreover, this bound is best possible. Here a gem is the graph that consists of an induced four-vertex path plus a vertex which is adjacent to all the vertices of that path.

Original languageEnglish (US)
Pages (from-to)527-542
Number of pages16
JournalJournal of Graph Theory
Volume95
Issue number4
DOIs
StatePublished - Dec 1 2020

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • P-free graphs
  • chromatic number
  • clique number
  • χ-boundedness

Fingerprint

Dive into the research topics of 'Coloring graphs with no induced five-vertex path or gem'. Together they form a unique fingerprint.

Cite this