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 language | English (US) |
---|---|
Pages (from-to) | 527-542 |
Number of pages | 16 |
Journal | Journal of Graph Theory |
Volume | 95 |
Issue number | 4 |
DOIs | |
State | Published - Dec 1 2020 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- P-free graphs
- chromatic number
- clique number
- χ-boundedness