On Reed's Conjecture in Triangle-Free Graphs
Vera Weil · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2010
The problem of finding the chromatic number of a graph G, i.e. the minimum number of colors needed to assign distinct colors to adjacent nodes of G, is NP-complete. However, there are some known bounds including the trivial lower bound χ(G) ≥ ω(G) and the upper bound provided by Brooks [2] χ(G) ≤ ∆(G) + 1, where χ(G) denotes the chromatic number, ∆(G) the maximum degree and ω(G) the number of nodes of a largest clique in G. In [6], Reed conjectured that