Yaşar Diner, ÖznurBaklan Şen,B.Yaşar Diner,Ö.Erlebach,T.2024-06-232024-06-2320240978-303149189-40302-9743https://doi.org/10.1007/978-3-031-49190-0_12https://hdl.handle.net/20.500.12469/5879Given a graph G= (V, E) and a list of available colors L(v) for each vertex v∈ V, where L(v) ⊆ { 1, 2, …, k}, List k -Coloring refers to the problem of assigning colors to the vertices of G so 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. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.eninfo:eu-repo/semantics/openAccess[No Keyword Available]Conference Object16818114422 LNCS10.1007/978-3-031-49190-0_122-s2.0-85180542749N/AQ2