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.

翻译：确定（$4K_1$, $C_4$）-自由图的着色复杂度是一个长期存在的开放问题。最近，Penev 证明了存在多项式时间算法可以对（$4K_1$, $C_4$, $C_6$）-自由图进行着色。本文中，我们将证明：若 $G$ 是一个包含 $C_6$ 的（$4K_1$, $C_4$, $P_6$）-自由图，则 $G$ 具有有界团宽度。为此，我们采用了一种新的界定团宽度的方法，该方法本身具有独立的研究价值。由此可得，存在多项式时间算法对（$4K_1$, $C_4$, $P_6$）-自由图进行着色。