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

Abstract Given a graph $$G=(V, E)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo>(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and a list of available colors L ( v ) for each vertex $$v\in V$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> </mml:mrow> </mml:math> , where $$L(v) \subseteq \{1, 2, \ldots , k\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> <mml:mo>⊆</mml:mo> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> , 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.