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, [STIX]x1D712(G) denotes its chromatic number and [STIX]x1D714(G) denotes the maximum size of a clique in G . We show that [STIX]x1D712(G)≤ 32[STIX]x1D714(G) floor for every ( P_5, gem)-free graph G .