A BOUND FOR THE CHROMATIC NUMBER OF ($P_{5}$, GEM)-FREE GRAPHS. Issue 2 (28th March 2019) - CAMERON, KATHIE; HUANG, SHENWEI; MERKEL, OWEN
Abstract : As usual, $P_{n}$ ( $n≥ 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)≤ \lfloor \frac{3}{2}\unicode[STIX]{x1D714}(G)\rfloor$ for every ( $P_{5}$, gem)-free graph $G$ .