Square-free graphs with no six-vertex induced path

05/14/2018

∙

by   T. Karthick, et al.

∙

0

∙

share

We elucidate the structure of (P_6,C_4)-free graphs by showing that every such graph either has a clique cutset, or a universal vertex, or belongs to several special classes whose structure is completely characterized. Using this result, we show that for any (P_6,C_4)-free graph G, the following hold: (i) 5ω(G)/4 and Δ(G) + ω(G) +1/2 are upper bounds for the chromatic number of G. Moreover, these bounds are tight. (ii) There is a polynomial-time algorithm that computes the chromatic number of G.