1 results
A BOUND FOR THE CHROMATIC NUMBER OF (
$P_{5}$, GEM)-FREE GRAPHS
- Part of
-
- Journal:
- Bulletin of the Australian Mathematical Society / Volume 100 / Issue 2 / October 2019
- Published online by Cambridge University Press:
- 28 March 2019, pp. 182-188
- Print publication:
- October 2019
-
- Article
-
- You have access
- Export citation
-
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$.
