A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS
Kathie Cameron, Shenwei Huang, Owen Merkel · Bulletin of the Australian Mathematical Society · 2019
As usual, $P_{n}$ ( $n\geq 1$ ) denotes the path on $n$ vertices. The gem is the graph consisting of a $P_{4}$ together with an additional vertex adjacent to each vertex of the $P_{4}$ . A graph is called ( $P_{5}$ , gem)-free if it has no induced subgraph isomorphic to a $P_{5}$ or to a gem. For a graph $G$ , $\unicode[STIX]{x1D712}(G)$ denotes its chromatic number and $\unicode[STIX]{x1D714}(G)$ denotes the maximum size of a clique in $G$ . We show that $\unicode[STIX]{x1D712}(G)\leq \lfloor \frac{3}{2}\unicode[STIX]{x1D714}(G)\rfloor$ for every ( $P_{5}$ , gem)-free graph $G$ .