标题： $C_5$-着色的极小障碍在遗传图类中 显示英文标题

标题： Minimal obstructions to $C_5$-coloring in hereditary graph classes

摘要： 对于图$G$和$H$，$G$的$H$-着色是从$V(G)$到$V(H)$的边保持映射。 注意，如果 $H$是三角形，那么 $H$-着色等价于 $3$-着色。 在本文中我们感兴趣的情况是 $H$是五顶点环 $C_5$。 一个到$C_5$-着色的最小障碍是一个没有$C_5$-着色的图，但其每个真诱导子图都有$C_5$-着色。 在本文中，我们关注在$F$-自由图中到$C_5$-着色的最小障碍，即排除某个固定的图$F$作为诱导子图的图。 设$P_t$表示具有$t$个顶点的路径，令$S_{a,b,c}$表示通过将路径$P_{a+1},P_{b+1},P_{c+1}$的一个端点进行合并得到的图。 我们证明，在$F$-free 图中，到$C_5$-coloring 的最小障碍只有有限多个，其中$F \in \{ P_8, S_{2,2,1}, S_{3,1,1}\}$并显式地确定了所有这些障碍。 这扩展了 Kamiński 和 Pstrucha [Discr. Appl. Math. 的结果。 261, 2019] 他们证明了存在有限数量的$P_7$-free 极小障碍物对$C_5$-着色，以及 D\k{e}bski 等人。 [ISAAC 2022 Proc.] 他们表明三角形是$S_{2,1,1}$-free 极小障碍物对$C_5$-着色的唯一障碍物。 我们通过构造一个无限族的最小障碍来补充我们的结果，这些障碍无法进行$C_5$-着色，同时它们也是$P_{13}$-自由和$S_{2,2,2}$-自由的。 我们还讨论了其他图$H$的$F$-自由的最小障碍的无限族，这些障碍无法进行$H$-着色。 显示英文摘要

摘要： 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_5$. A minimal obstruction to $C_5$-coloring is a graph that does not have a $C_5$-coloring, but every proper induced subgraph thereof has a $C_5$-coloring. In this paper we are interested in minimal obstructions to $C_5$-coloring in $F$-free graphs, i.e., graphs that exclude some fixed graph $F$ as an induced subgraph. Let $P_t$ denote the path on $t$ vertices, and let $S_{a,b,c}$ denote the graph obtained from paths $P_{a+1},P_{b+1},P_{c+1}$ by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to $C_5$-coloring among $F$-free graphs, where $F \in \{ P_8, S_{2,2,1}, S_{3,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_7$-free minimal obstructions to $C_5$-coloring, and of D\k{e}bski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique $S_{2,1,1}$-free minimal obstruction to $C_5$-coloring. We complement our results with a construction of an infinite family of minimal obstructions to $C_5$-coloring, which are simultaneously $P_{13}$-free and $S_{2,2,2}$-free. We also discuss infinite families of $F$-free minimal obstructions to $H$-coloring for other graphs $H$.