Square-free graphs with no six-vertex induced path
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.
READ FULL TEXT