Author/Authors :
Esperet، نويسنده , , Louis and Lemoine، نويسنده , , Laetitia and Maffray، نويسنده , , Frédéric and Morel، نويسنده , , Grégory، نويسنده ,
Abstract :
Gyárfás conjectured that for any tree T every T -free graph G with maximum clique size ω ( G ) is f T ( ω ( G ) ) -colorable, for some function f T that depends only on T and ω ( 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 P 5 ( 2 ) = 3 and f P 5 ( q ) ≤ 3 q − 1 . We prove here that f P 5 ( 3 ) = 5 .
