论文标题
列表$ k $ - 颜色$ p_t $ - 免费图形：mim宽度的观点
List $k$-Colouring $P_t$-Free Graphs: a Mim-width Perspective
论文作者
论文摘要
图$ g =（v，e）$的颜色是映射$ c \ colon v \ to \ {1,2，\ ldots \} $，这样每两个相邻的顶点$ u $ $ $ u $ and $ v $ g $ $ c（u）\ neq c（v）$。 {\ sclist $ k $ -colouring}问题是确定图形$ g =（v，e）$是否列表$ l（u）\ subseteq \ {1，\ ldots，\ ldots，\ ldots，k \} $ in V $中的每个$ u \ in v $中的每个$ u \ in v $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ in l（u）$ in l（u）$ c。令$ p_t $成为$ t $顶点的路径，让$ k_ {1，s}^1 $成为从$（s+1）$ - 顶点星$ k_ {1，s} $获得的图表，通过将其每个边缘精确地细分一次。可解决的$（k_ {1，s}^1，p_t）$ - 每$ t \ geq 1 $和$ s \ geq 1 $的免费图形。我们将他们的结果推广到每$ k \ geq 1 $列出$ k $彩色。 Our result also generalizes the known result that for every $k\geq 1$ and $s\geq 0$, List $k$-Colouring is polynomial-time solvable for $(sP_1+P_5)$-free graphs, which was proven for $s=0$ by Hoàng, Kamiński, Lozin, Sawada, and Shu (Algorithmica 2010) and for every $s\geq 1$ Couturier，Golovach，Kratsch和Paulusma（算法，2015年）。我们通过证明潜在宽度参数的界限来显示我们的结果。也就是说，我们表明，对于每$ k \ geq 1 $，$ s \ geq 1 $，$ t \ geq 1 $，$（k_k，k_ {1，s}^1，p_t）$ - 免费图形的限制了mim宽度，并且相应的分支分解是“快速计算的”图表。
A colouring of a graph $G=(V,E)$ is a mapping $c\colon V\to \{1,2,\ldots\}$ such that $c(u)\neq c(v)$ for every two adjacent vertices $u$ and $v$ of $G$. The {\sc List $k$-Colouring} problem is to decide whether a graph $G=(V,E)$ with a list $L(u)\subseteq \{1,\ldots,k\}$ for each $u\in V$ has a colouring $c$ such that $c(u)\in L(u)$ for every $u\in V$. Let $P_t$ be the path on $t$ vertices and let $K_{1,s}^1$ be the graph obtained from the $(s+1)$-vertex star $K_{1,s}$ by subdividing each of its edges exactly once.Recently, Chudnovsky, Spirkl and Zhong (DM 2020) proved that List $3$-Colouring is polynomial-time solvable for $(K_{1,s}^1,P_t)$-free graphs for every $t\geq 1$ and $s\geq 1$. We generalize their result to List $k$-Colouring for every $k\geq 1$. Our result also generalizes the known result that for every $k\geq 1$ and $s\geq 0$, List $k$-Colouring is polynomial-time solvable for $(sP_1+P_5)$-free graphs, which was proven for $s=0$ by Hoàng, Kamiński, Lozin, Sawada, and Shu (Algorithmica 2010) and for every $s\geq 1$ by Couturier, Golovach, Kratsch and Paulusma (Algorithmica 2015). We show our result by proving boundedness of an underlying width parameter. Namely, we show that for every $k\geq 1$, $s\geq 1$, $t\geq 1$, the class of $(K_k,K_{1,s}^1,P_t)$-free graphs has bounded mim-width and that a corresponding branch decomposition is "quickly computable" for these graphs.
