Colouring Probe H-Free Graphs

The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G, P, N) consists of a graph G = (V, E), together with a set P ⊆ V of probes and an independent set N = V \ P of non-probes, such that G + F is H-free for some edge set F ⊆ (^N₂). We show the following: We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. We fully classify 3-Colouring on partitioned probe Pt-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on Pt-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P5-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P5-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P5-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P5-free graphs but NP-complete for partitioned probe P5-free graphs. In particular, unlike the class of 3-colourable P5-free graphs, the class of 3-colourable probe P5-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P5-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P5-free graphs.