List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
Abstract
Abstract Given a graph $$G=(V, E)$$ G = ( V , E ) and a list of available colors L ( v ) for each vertex $$v\in V$$ v ∈ V , where $$L(v) \subseteq \{1, 2, \ldots , k\}$$ L ( v ) ⊆ { 1 , 2 , … , 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.
Fields of Study & Subjects
Nuclear Receptors and Signaling
Publication details
- Journal / source
- Journal of Combinatorial Optimization
- Publisher
- Springer Science and Business Media LLC
- Volume
- 51
- Issue
- 5
- Pages
- 47–47
- Publication date
- 16 May 2026
- Language
- EN