Colouring Probe $H$-Free Graphs

Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen

The NP-complete problems Colouring and k-Colouring $(k\ge 3$) are well studied on $H$-free graphs, i.e., graphs that do not contain some fixed graph $H$ as an induced subgraph. We…