Reed's conjecture on some special classes of graphs

Abstract

Reed conjectured that for any graph $G$, $\chi (G)\le \lceil \frac{\omega (G)+\Delta (G)+1}{2}\rceil$, where $\chi (G)$, $\omega (G)$, and $\Delta (G)$ respectively denote the chromatic number, the clique number and the maximum degree of $G$. In this paper, we verify this conjecture for some special classes of graphs, in particular for subclasses of $P_5$-free graphs or $Chair$-free graphs.

Submitted to Discrete Mathematics

References in corpus (1)

• Reed's Conjecture on hole expansions