论文标题
遗传图类中的计算同构：5轮的特殊情况和没有长爪的图形
Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws
论文作者
论文摘要
对于图形$ g $和$ h $，$ h $颜色为$ g $的$ h $颜色是$ v（g）$到$ v（h）$的边缘保留映射。在$ h $颜色的问题中，图$ h $是固定的，我们询问实例图$ g $是否允许$ h $颜色。此问题的概括是$ h $ -Coloringext，其中一些$ g $的顶点已经映射到$ h $的顶点，我们询问该部分映射是否可以扩展到$ h $颜色。 我们研究了$ h $颜色的$ f $ fule图的变体的复杂性，即不包括固定图$ f $作为诱导子图的图形。对于整数$ a，b，c \ geq 1 $，by $ s_ {a，b，c} $，我们表示通过识别$ a+1 $，$ b+1 $和$ c+1 $ dertices的三个endvertex的图表。对于奇数$ k \ geq 5 $，由$ w_k $，我们通过添加通用顶点来表示从$ k $ cycle获得的图。 作为我们的主要算法结果，我们表明$ W_5 $ -COLORONEXT是$ S_ {2,1,1} $ - 免费图形的多项式时间。对于拍摄$ h $ $ h $的诱发子图，该结果表现出有趣的非单调性，为$ h $ coloringext。实际上，$ w_5 $包含一个三角形，$ k_3 $ - 彩色，即经典的3色，已在无爪状（即$ s_ {1,1,1,1} $ - 免费）图中已有NP-HARD。 我们的算法基于两个主要观察结果： 1。$ w_5 $ -coloringext in $ s_ {2,1,1} $ - 可以在多项式时间中缩小到查找独立集与所有三角形的问题的变体中的多项式时间，并且 2。后一个问题可以在$ s_ {2,1,1} $ - 免费图形中以多项式时间解决。 我们用几个负面的结果补充了这种算法结果。特别是，我们表明$ w_5 $ -coloringext是$ s_ {3,3,3} $ - 免费图形的np-hard。这又是罕见的，因为通常在$ s_ {a，b，c} $中np-hard的问题 - 对于某些常数$ a，b，c $的免费图表已经很难。
For graphs $G$ and $H$, an $H$-coloring of $G$ is an edge-preserving mapping from $V(G)$ to $V(H)$. In the $H$-Coloring problem the graph $H$ is fixed and we ask whether an instance graph $G$ admits an $H$-coloring. A generalization of this problem is $H$-ColoringExt, where some vertices of $G$ are already mapped to vertices of $H$ and we ask if this partial mapping can be extended to an $H$-coloring. We study the complexity of variants of $H$-Coloring in $F$-free graphs, i.e., graphs excluding a fixed graph $F$ as an induced subgraph. For integers $a,b,c \geq 1$, by $S_{a,b,c}$ we denote the graph obtained by identifying one endvertex of three paths on $a+1$, $b+1$, and $c+1$ vertices, respectively. For odd $k \geq 5$, by $W_k$ we denote the graph obtained from the $k$-cycle by adding a universal vertex. As our main algorithmic result we show that $W_5$-ColoringExt is polynomial-time solvable in $S_{2,1,1}$-free graphs. This result exhibits an interesting non-monotonicity of $H$-ColoringExt with respect to taking induced subgraphs of $H$. Indeed, $W_5$ contains a triangle, and $K_3$-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., $S_{1,1,1}$-free) graphs. Our algorithm is based on two main observations: 1. $W_5$-ColoringExt in $S_{2,1,1}$-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2. the latter problem can be solved in polynomial time in $S_{2,1,1}$-free graphs. We complement this algorithmic result with several negative ones. In particular, we show that $W_5$-ColoringExt is NP-hard in $S_{3,3,3}$-free graphs. This is again uncommon, as usually problems that are NP-hard in $S_{a,b,c}$-free graphs for some constant $a,b,c$ are already hard in claw-free graphs.
