Minimal obstructions to C₅-coloring in hereditary graph classes

For graphs G and H, an H-coloring of G is an edge-preserving mapping from $V(G)$ to $V(H)$. Note that if H is the triangle, then H-colorings are equivalent to $3$-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i.e., graphs that exclude some fixed graph F as an induced subgraph. Let Pₜ denote the path on t vertices, and let Sa,b,c denote the graph obtained from paths Pₐ₊₁,Pb+1,Pc+1 by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ \ P₈, S2,2,1, S3,1,1\ and explicitly determine all such obstructions. This extends the results of Kami\'nski and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of D{e}bski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique S2,1,1-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P₁₃-free and S2,2,2-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.