On 3-colourability of $(bull, H)$-free graphs

The $3$-colourability problem is a well-known NP-complete problem and it remains NP-complete for $bull$-free graphs, where $bull$ is the graph consisting of K₃ with two pendant edges attached to two of its vertices. In this paper we study $3$-colourability of $(bull,H)$-free graphs for several graphs H. We show that these graphs are $3$-colourable or contain an induced odd wheel W₂ₚ₊₁ for some p≥ 2 or a spindle graph M₃ₚ₊₁ for some p≥ 1. Moreover, for all our results we can provide certifying algorithms that run in polynomial time.