Article contents
A BOUND FOR THE CHROMATIC NUMBER OF ($P_{5}$, GEM)-FREE GRAPHS
Published online by Cambridge University Press: 28 March 2019
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$.
MSC classification
- Type
- Research Article
- Information
- Bulletin of the Australian Mathematical Society , Volume 100 , Issue 2 , October 2019 , pp. 182 - 188
- Copyright
- © 2019 Australian Mathematical Publishing Association Inc.
Footnotes
Shenwei Huang is the corresponding author. The research of the first author was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant RGPIN-2016-06517; the research of the second author was supported by the National Natural Science Foundation of China grant 11801284; the research of the third author was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant RGPIN-2016-06517 and an NSERC Undergraduate Student Research Award.
References
- 8
- Cited by