论文标题
列表 - 三颜色$ p_t $ - 没有诱发的1个$ k_ {1，s} $
List-three-coloring $ P_t $-free graphs with no induced 1-subdivision of $ K_{1,s} $
论文作者
论文摘要
让$ s $和$ t $为正整数。我们使用$ p_t $用$ t $顶点和$ k_ {1，s} $表示路径，以分别用大小$ 1 $和$ s $的零件表示完整的两部分图。 $ k_ {1，s} $的一单分割是通过替换每个边缘$ \ {u，v \} $的$ k_ {1，s} $的每个边缘$ \ \ \ {u，w \} $和新Vertex $ w $的$ k_ {1，s} $。在本文中，我们给出了列表的第三个颜色问题的多项式时间算法，仅限于$ p_t $ - free Graph的类别，而没有$ k_ {1，s} $的1个补充。
Let $s$ and $t$ be positive integers. We use $P_t$ to denote the path with $t$ vertices and $K_{1,s}$ to denote the complete bipartite graph with parts of size $1$ and $s$ respectively. The one-subdivision of $K_{1,s}$ is obtained by replacing every edge $\{u,v\}$ of $K_{1,s}$ by two edges $\{u,w\}$ and $\{v,w\}$ with a new vertex $w$. In this paper, we give a polynomial-time algorithm for the list-three-coloring problem restricted to the class of $P_t$-free graph with no induced 1-subdivision of $K_{1,s}$.
