论文标题
在列表k-coloring凸两部分图
On List k-Coloring Convex Bipartite Graphs
论文作者
论文摘要
列表k-coloring（li k-col）是决策问题，询问给定图是否允许与给定列表分配的适当颜色兼容其在{1,2，..，k}中的颜色的顶点。已知该问题即使在3个规则平面两分图的类别中，对于K = 3，对于K = 3也是NP，对于弦弦两分裂图类别中的K = 4。 2015年，黄，约翰逊和保卢斯玛要求在弦弦二分之一的类别中李3-Col的复杂性。在本文中，我们通过表明李k-Col在凸双方图类别中是多项式，给出了部分答案。我们首先表明，双方双方图允许多键顺序，扩展了eNright，Stewart和Tardos（2014）的多项式算法的类别，可以将其应用于该问题。我们提供了一种动态编程算法，以在凸两部分图的CALS中求解Li K-Col。最后，我们展示了如何修改我们的算法以求解凸双方图上更通用的李H-Col问题。
List k-Coloring (Li k-Col) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..,k}. The problem is known to be NP-hard even for k=3 within the class of 3-regular planar bipartite graphs and for k=4 within the class of chordal bipartite graphs. In 2015, Huang, Johnson and Paulusma asked for the complexity of Li 3-Col in the class of chordal bipartite graphs. In this paper we give a partial answer to this question by showing that Li k-Col is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the Li k-Col in the calss of convex bipartite graphs. Finally we show how our algorithm can be modified to solve the more general Li H-Col problem on convex bipartite graphs.
