On the structure of ($4K_1$, $C_4$, $P_6$)-free graphs
By: Chính T. Hoàng, Ramin Javadi, Nicolas Trotignon
Potential Business Impact:
Helps computers color maps faster.
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.
Similar Papers
Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs
Computational Complexity
Helps solve a hard coloring puzzle for computers.
Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
Computational Complexity
Makes graph coloring problems easier to solve.
Independent sets and colorings of $K_{t,t,t}$-free graphs
Combinatorics
Helps computers color maps with fewer colors.