Some results on Reed's Conjecture about ω, Δ, and χ with respect to α

Let G be a graph of order n with chromatic number chi, maximum degree Delta, clique number omega and independence number alpha. In 1998 Reed conjectured that chi is bounded from above by left perpendicular Delta + omega + 1/2 right perpendicular. We will present some partial solutions for this conjecture with respect to alpha. For instance, we will verify Reed's Conjecture for graphs with independence number alpha = 2, for graphs with maximum degree Delta >= n - alpha - 4, and for triangle-free graphs having maximum degree Delta >= 8(n-alpha) + 118/21. In addition, we will prove the general upper bound chi <= 1/3 (n - alpha + omega + 2 + Delta+omega+1/2). (C) 2009 Elsevier B.V. All rights reserved.