On Reed’s Conjecture about ω,Δ and χ
Bert Randerath, Ingo Schiermeyer · Birkhäuser Basel eBooks · 2006
For a given graph G, the clique number ω(G), the chromatic number χ(G) and the maximum degree Δ(G) satisfy ω(G) ≤ χ(G) ≤ Δ(G)+1. Brooks showed that complete graphs and odd cycles are the only graphs attaining the upper bound Δ(G)+1. Reed conjectured \( \chi (G) \leqslant \left\lceil {\tfrac{{\Delta + 1 + \omega }} {2}} \right\rceil \) . In this paper we will present some partial solutions for this conjecture.