Show simple item record

dc.contributor.authorDiaz, Josep
dc.contributor.authorDiner, Öznur Yaşar
dc.contributor.authorSerna, Maria
dc.contributor.authorOriol, Serra
dc.description.abstractList k-Coloring (Lik-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 Lik-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 et al. (SIAM J Discrete Math 28(4):1675–1685, 2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the Lik-Col in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LiH-Col problem on convex bipartite graphs.en_US
dc.publisherSpringer Natureen_US
dc.subjectBiconvex bipartite graphsen_US
dc.subjectConvex bipartiteen_US
dc.subjectList coloringen_US
dc.titleOn list k-coloring convex bipartite graphsen_US
dc.typeBook chapteren_US
dc.relation.journalAIRO Springer Seriesen_US
dc.contributor.khasauthorDiner, Özgür Yaşaren_US

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record