### ?

## The vertex colourability problem for {claw,butterfly}-free graphs is polynomial-time solvable

The vertex colourability problem is to determine, for a given graph and a given natural *k*, whether it is possible to split the graph’s vertex set into at most *k* subsets, each of pairwise non-adjacent vertices, or not. A hereditary class is a set of simple graphs, closed under deletion of vertices. Any such a class can be defined by the set of its forbidden induced subgraphs. For all but four hereditary classes, defined by a pair of connected five-vertex induced prohibitions, the complexity status of the vertex colourability problem is known. In this paper, we reduce the number of the open cases to three, by showing polynomial-time solvability of the problem for {claw,butterfly}{claw,butterfly}-free graphs. A *claw* is the star graph with three leaves, a *butterfly* is obtained by coinciding a vertex in a triangle with a vertex in another triangle.