List 3-coloring on comb-convex and caterpillar-convex bipartite graphs

Given a graph $G=(V,E)$ and a list of available colors L(v) for each vertex $v\in V$ , where $L\left(v\right)\subseteq \{1,2,\dots ,k\}$ , List k-Coloring refers to the problem of assigning colors to the vertices of G such that each vertex receives a color from its own list and no two neighboring vertices receive the same color. The decision version of the problem List 3-Coloring is NP-complete even for bipartite graphs, and its complexity on comb-convex bipartite graphs has been an open problem. We give a polynomial-time algorithm to solve List 3-Coloring for caterpillar-convex bipartite graphs, a superclass of comb-convex bipartite graphs. We also give a polynomial-time recognition algorithm for the class of caterpillar-convex bipartite graphs.