Solving the clique cover problem on (bull, $C_4$)-free graphs

Abstract

We give an $O(n^4)$ algorithm to find a minimum clique cover of a (bull, $C_4$)-free graph, or equivalently, a minimum colouring of a (bull, $2K_2$)-free graph, where $n$ is the number of vertices of the graphs.

References in corpus (1)

• Powers of Tensors and Fast Matrix Multiplication

Cited by in corpus (1)

• Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide