Coloring graphs with no induced five-vertex path or gem

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

Research output: Contribution to journalArticle

Abstract

For a graph G, let χ(G) and ω(G), respectively, denote the chromatic number and clique number of G. We give an explicit structural description of (P5, gem-free graphs, and show that every such graph G 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)
JournalJournal of Graph Theory
DOIs
StateAccepted/In press - Jan 1 2020

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • chromatic number
  • clique number
  • P-free graphs
  • χ-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