There Are Finitely Many 5‐Vertex‐Critical (P6,bull)‐Free Graphs

ABSTRACT In this paper, we are interested in 4‐colouring algorithms for graphs that do not contain an induced path on six vertices nor an induced bull, that is, the graph with vertex set and edge set . Such graphs are referred to as ‐free graphs. A graph is ‐ vertex‐critical if , and every proper induced subgraph of has . In the current paper, we investigate the structure of 5‐vertex‐critical ‐free graphs and show that there are only finitely many such graphs, thereby answering a question of Maffray and Pastor. A direct corollary of this is that there exists a polynomial‐time algorithm to decide if a ‐free graph is 4‐colourable such that this algorithm can also provide a certificate that can be verified in polynomial time and serves as a proof of 4‐colourability or non‐4‐colourability.