The chromatic number of {P5, K4}-free graphs

Gyarfas conjectured that for any tree T every T-free graph G with maximum clique size omega(G) is f(T)(omega(G))-colorable, for some function f(T) that depends only on T and omega(G). Moreover, he proved the conjecture when T is the path P-k on k vertices. In the case of P-5, the best values or bounds known so far are f(P5) (2) = 3 and f(P5) (q) <= 3(q-1). We prove here that f(P5) (3) = 5. (C) 2012 Elsevier B.V. All rights reserved.