Three complexity results on coloring P k -free graphs
Three complexity results on coloring P k -free graphs
复制标题
着色 P k 无图的三种复杂性结果
DOI：
10.1016/j.ejc.2011.12.008
复制
发表时间：
2013
影响因子：
1
通讯作者：
Broersma H
中科院分区：
文献类型：
--
作者：
Broersma H
我们证明了三个限制在Pk-free图上的顶点着色问题的复杂性结果，即，不包含k个顶点上的路径的图作为导出子图。首先，我们证明了5-着色的预着色扩展版本在P6-free图中仍然是NP-完全的。Hoàng等人的最新结果暗示了这个问题在P5-free图上是多项式可解的。其次，我们证明了P6-free图的3-染色的预染色扩张是多项式可解的。这意味着一个比Randerath和Schiermeyer给出的算法更简单的检查P6-free图的3-可染性的算法。最后，我们证明了P7-free图的6-染色是NP-完全的。这个问题对于P5-free图是多项式可解的，而对于P8-free图是NP-完全的，所以仍然有一个开放的情况。
We prove three complexity results on vertex coloring problems restricted to Pk-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to P6-free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on P5-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for P6-free graphs. This implies a simpler algorithm for checking the 3-colorability of P6-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for P7-free graphs. This problem was known to be polynomially solvable for P5-free graphs and NP-complete for P8-free graphs, so there remains one open case.