arXiv Analytics

Sign in

arXiv:2006.02015 [math.CO]AbstractReferencesReviewsResources

Coloring $(P_5, \text{gem})$-free graphs with $Δ-1$ colors

Daniel W. Cranston, Hudson Lafayette, Landon Rabern

Published 2020-06-03Version 1

The Borodin-Kostochka Conjecture states that for a graph $G$, if $\Delta(G) \geq 9$ and $\omega(G) \leq \Delta(G)-1$, then $\chi(G)\leq\Delta(G) -1$. We prove the Borodin-Kostochka Conjecture for $(P_5, \text{gem})$-free graphs, i.e., graphs with no induced $P_5$ and no induced $K_1\vee P_4$.

Comments: 8 pages, 6 figures
Categories: math.CO
Subjects: 05C15
Related articles: Most relevant | Search more
arXiv:2102.13458 [math.CO] (Published 2021-02-26)
Chromatic bounds for the subclasses of $pK_2$-free graphs
arXiv:2405.18455 [math.CO] (Published 2024-05-28)
Coloring some $(P_6,C_4)$-free graphs with $Δ-1$ colors
arXiv:1901.06985 [math.CO] (Published 2019-01-21)
A note on Hadwiger's Conjecture for $W_5$-free graphs with independence number two

Links

Toolbox