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.
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- chromatic number
- clique number
- P-free graphs