A BOUND FOR THE CHROMATIC NUMBER OF ($P_{5}$, GEM)-FREE GRAPHS. Issue 2 (28th March 2019)

• Record Type: Journal Article
• Authors: CAMERON, KATHIE; HUANG, SHENWEI; MERKEL, OWEN
• Is Part Of: Bulletin of the Australian Mathematical Society. Volume 100:Issue 2(2019)
• Page Start: 182
• Page End: 188
• Publication Date: 2019-03-28
• Subjects: primary 05C15, -- secondary 05C75, -- 05C85, -- 68R10; graph colouring, -- hereditary classes, -- chi-bound; Mathematics -- Societies, etc; Mathematics -- Periodicals; 510.5
• DOI: 10.1017/S0004972719000352
• Languages: English
• ISSNs: 0004-9727

Abstract

Abstract : 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$ .