On the chromatic number of P5-free graphs with no large intersecting cliques.

A graph G is called (H 1 , H 2) -free if G contains no induced subgraph isomorphic to H 1 or H 2 . Let P k be a path with k vertices and C s , t , k ( s ≤ t ) be a graph consisting of two intersecting complete graphs K s + k and K t + k with exactly k common vertices. In this paper, using an iterative method, we prove that the class of (P 5 , C s , t , k) -free graphs with clique number ω has a polynomial χ -binding function f (ω) = c (s , t , k) ω max { s , k } . In particular, we give two improved chromatic bounds: every (P 5 , b u t t e r f l y) -free graph G has χ (G) ≤ 3 2 ω (G) (ω (G) - 1) ; every (P 5 , C 1 , 3) -free graph G has χ (G) ≤ 9 ω (G) . [ABSTRACT FROM AUTHOR]