List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs

Baklan Sen, Banu; Diner, Öznur Yasar; Erlebach, Thomas

Abstract

Given 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.

Citation

Baklan Sen, B., Diner, Ö. Y., & Erlebach, T. (2023, December). List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs. Presented at 29th International Computing and Combinatorics Conference (COCOON 2023), Honolulu, Hawaii, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 29th International Computing and Combinatorics Conference (COCOON 2023)
• Start Date: Dec 15, 2023
• End Date: Dec 17, 2023
• Acceptance Date: Aug 15, 2023
• Online Publication Date: Dec 9, 2023
• Publication Date: Dec 9, 2023
• Deposit Date: Sep 4, 2023
• Publicly Available Date: Dec 10, 2024
• Print ISSN: 0302-9743
• Publisher: Springer Berlin Heidelberg
• Volume: 14422
• Pages: 168-181
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Proceedings of the 29th International Computing and Combinatorics Conference (COCOON 2023)
• ISBN: 9783031491894
• DOI: https://doi.org/10.1007/978-3-031-49190-0_12
• Public URL: https://durham-repository.worktribe.com/output/1729210