Reed's conjecture on some special classes of graphs
Jean‐Luc Fouquet, Jean-Marie Vanherpe · arXiv (Cornell University) · 2012
Reed conjectured that for any graph $G$, $χ(G) \leq \lceil \frac{ω(G)+Δ(G)+1}{2}\rceil$, where $χ(G)$, $ω(G)$, and $Δ(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.