Title: Certifying coloring algorithms for graphs without long induced paths,
Abstract: 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 $k, t>0$ and a graph $H$ there are finitely many
subgraph minimal graphs with no induced $P_k$ and $K_{t,t}$ that are not
$H$-colorable and (2) for any integer $k>4$ there are finitely many subgraph
minimal graphs with no induced $P_k$ that are not $C_{k-2}$-colorable.
The former generalizes the result of Hell and Huang [Complexity of coloring
graphs without paths and cycles, Discrete Appl. Math. 216: 211--232 (2017)] and
the latter extends a result of Bruce, Hoang, and Sawada [A certifying algorithm
for 3-colorability of $P_5$-Free Graphs, ISAAC 2009: 594--604]. Both our
results lead to polynomial-time certifying algorithms for the corresponding
coloring problems.