论文标题
着色$（SP_1+P_5）$ - 免费图形：MIM宽度的观点
Colouring $(sP_1+P_5)$-Free Graphs: a Mim-Width Perspective
论文作者
论文摘要
我们证明，$（k_t，sp_1+p_5）$ - 免费图形的每个$ s \ geq 0 $和$ t \ geq 1 $都有限制的mim宽度，并且有一个多项式时间算法，鉴于班上的图形，可以计算出一个不变的mim-fidth的分支分解。大量的\ np完整图问题成为有界MIM宽度的图形类别的多项式时间溶解，并且可以快速计算分支分解。 $ k $颜色的问题就是这样一个问题的一个例子。对于此问题，我们可以假设输入图为$ k_ {k+1} $ - 免费。然后，由于我们的结果，我们获得了已知结果的新证明，即对于每个固定的$ k \ geq 1 $和$ s \ geq 0 $，$ k $ - 颜色是可解决的多项式时间（SP_1+P_5）$ - 免费图形。实际上，我们的发现表明，这种多项式时间算法的根本原因是该类具有MIM宽度。
We prove that the class of $(K_t,sP_1+P_5)$-free graphs has bounded mim-width for every $s\geq 0$ and $t\geq 1$, and that there is a polynomial-time algorithm that, given a graph in the class, computes a branch decomposition of constant mim-width. A large number of \NP-complete graph problems become polynomial-time solvable on graph classes with bounded mim-width and for which a branch decomposition is quickly computable. The $k$-Colouring problem is an example of such a problem. For this problem, we may assume that the input graph is $K_{k+1}$-free. Then, as a consequence of our result, we obtain a new proof for the known result that for every fixed $k\geq 1$ and $s\geq 0$, $k$-Colouring is polynomial-time solvable for $(sP_1+P_5)$-free graphs. In fact, our findings show that the underlying reason for this polynomial-time algorithm is that the class has bounded mim-width.
