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 S₀, ₁, ₂ denote the graph obtained from paths P₀+₁, P₁+₁, P₂+₁ 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₈, S₂, ₂, ₁, S₃, ₁, ₁\ 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 Debski et al. ISAAC 2022 Proc. who showed that the triangle is the unique S₂, ₁, ₁-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 S₂, ₂, ₂-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.