论文标题
$ c_k $的复杂性 - 在遗传类别的图中颜色
Complexity of $C_k$-coloring in hereditary classes of graphs
论文作者
论文摘要
对于图$ f $，图$ g $是\ emph {$ f $ -free}，如果它不包含诱导子图的同构为$ f $。对于两个图$ g $和$ h $，$ g $的a \ emph {$ h $ - 颜色}是映射$ f：v（g）\ rightArrow v（h）$，因此对于每个edge $ uv \ in E（g）$中的每个边缘$ uv \ in（g）$，它认为$ f（u）f（u）f（u）f（u）f（u）f（u）f（u）f（u）f（u）f（v）\ in E（h）$。我们对问题的复杂性$ h $ - {\ sc着色}感兴趣，该}要求存在$ h $ - 输入图$ g $的颜色。特别是，我们考虑$ h $ - {\ sc coloring} $ f $ - free Graphs，其中$ f $是固定的图形，$ h $是一个奇怪的长度周期。这个问题与确定$ p_t $ p_t $ free-free Graphers的3- {\ sc Coloring}的复杂性的众所周知的开放问题密切相关。 我们表明，对于每个奇数$ k \ geq 5 $ $ c_k $ - {\ sc coloring}问题，即使在列表变体中，也可以在多项式时间中以$ p_9 $ - free Graphs求解。该算法扩展了$ c_k $ - {\ sc coloring}的列表版本的情况，其中$ k $是偶数长度至少10。 另一方面，我们证明，如果$ f $的某些组成部分不是一个细分的爪子的子图，那么以下问题在$ f $ - free Graphs中是np-complete：a）$ c_k $ - {\ sc coloring}的扩展版本的每个奇数$ k \ geq 5 $，b）$ c_k $ c_k $ c $ c $ c $ cody bes of c_ k \ geq geq for con fors c_ for cod-ege bes for
For a graph $F$, a graph $G$ is \emph{$F$-free} if it does not contain an induced subgraph isomorphic to $F$. For two graphs $G$ and $H$, an \emph{$H$-coloring} of $G$ is a mapping $f:V(G)\rightarrow V(H)$ such that for every edge $uv\in E(G)$ it holds that $f(u)f(v)\in E(H)$. We are interested in the complexity of the problem $H$-{\sc Coloring}, which asks for the existence of an $H$-coloring of an input graph $G$. In particular, we consider $H$-{\sc Coloring} of $F$-free graphs, where $F$ is a fixed graph and $H$ is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3-{\sc Coloring} of $P_t$-free graphs. We show that for every odd $k \geq 5$ the $C_k$-{\sc Coloring} problem, even in the list variant, can be solved in polynomial time in $P_9$-free graphs. The algorithm extends for the case of list version of $C_k$-{\sc Coloring}, where $k$ is an even number of length at least 10. On the other hand, we prove that if some component of $F$ is not a subgraph of a subdividecd claw, then the following problems are NP-complete in $F$-free graphs: a)extension version of $C_k$-{\sc Coloring} for every odd $k \geq 5$, b) list version of $C_k$-{\sc Coloring} for every even $k \geq 6$.
