Diaz, JosepDiner, Öznur YaşarSerna, MariaOriol, Serra2021-07-172021-07-17202162523-70472523-7047https://hdl.handle.net/20.500.12469/4071List 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.eninfo:eu-repo/semantics/openAccessBiconvex bipartite graphsConvex bipartiteList coloringBook Part1526510.1007/978-3-030-63072-0_22-s2.0-85104003988N/AN/A