On the structure of ($4K_1$, $C_4$, $P_6$)-free graphs

Abstract

Determining the complexity of colouring ($4K_1,C_4$)-free graph is a long open problem. Recently Penev showed that there is a polynomial-time algorithm to colour a ($4K_1,C_4,C_6$)-free graph. In this paper, we will prove that if $G$ is a ($4K_1,C_4,P_6$)-free graph that contains a $C_6$, then $G$ has bounded clique-width. To this purpose, we use a new method to bound the clique-width, that is of independent interest. As a consequence, there is a polynomial-time algorithm to colour ($4K_1,C_4,P_6$)-free graphs.