Coloring graphs with no induced five-vertex path or gem
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 (P_5,gem)-free graphs, and show that every such graph G satisfies χ(G)<5ω(G)/4. Moreover, this bound is best possible.
READ FULL TEXT