Chromatic number of P5-free graphs: Reed's conjecture

In this paper we study the chromatic number of P-5-free graphs. In 1998, Reed proposed the following Conjecture: Every graph G with chromatic number chi(G), clique number omega(G) and maximum degree Delta(G) satisfies chi(G) <= [omega(G)+Delta(G)+1/2]. Reed's conjecture is still open in general. Our main result is that Reed's conjecture holds for the class of P-5-free graphs in the asymptotic sense. We will also show that Reed's conjecture is true for many special P-5-free graphs. Moreover, we will present polynomial x-binding functions for these subclasses. (C) 2015 Elsevier B.V. All rights reserved.