Certifying coloring algorithms for graphs without long induced paths

Marcin Kamiński, Anna Pstrucha

Let $P_k$ be a path, $C_k$ a cycle on $k$ vertices, and $K_{k,k}$ a complete bipartite graph with $k$ vertices on each side of the bipartition. We prove that (1) for any integers $…