On List K-Coloring Convex Bipartite Graphs

dc.contributor.author Diaz, Josep
dc.contributor.author Yaşar Diner, Öznur
dc.contributor.author Diner, Öznur Yaşar
dc.contributor.author Serna, Maria
dc.contributor.author Oriol, Serra
dc.contributor.other Computer Engineering
dc.date.accessioned 2021-07-17T17:27:20Z
dc.date.available 2021-07-17T17:27:20Z
dc.date.issued 2021
dc.description.abstract List k-Coloring (Lik-Col) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1, 2, …, k}. The problem is known to be NP-hard even for k = 3 within the class of 3-regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of Li 3-Col in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that Lik-Col is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright et al. (SIAM J Discrete Math 28(4):1675–1685, 2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the Lik-Col in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LiH-Col problem on convex bipartite graphs. en_US
dc.identifier.citationcount 6
dc.identifier.doi 10.1007/978-3-030-63072-0_2 en_US
dc.identifier.endpage 26 en_US
dc.identifier.issn 2523-7047 en_US
dc.identifier.issn 2523-7047
dc.identifier.scopus 2-s2.0-85104003988 en_US
dc.identifier.startpage 15 en_US
dc.identifier.uri https://hdl.handle.net/20.500.12469/4071
dc.identifier.volume 5 en_US
dc.institutionauthor Diner, Özgür Yaşar en_US
dc.language.iso en en_US
dc.publisher Springer Nature en_US
dc.relation.journal AIRO Springer Series en_US
dc.relation.publicationcategory Kitap Bölümü - Uluslararası en_US
dc.rights info:eu-repo/semantics/openAccess en_US
dc.scopus.citedbyCount 7
dc.subject Biconvex bipartite graphs en_US
dc.subject Convex bipartite en_US
dc.subject List coloring en_US
dc.title On List K-Coloring Convex Bipartite Graphs en_US
dc.type Book Part en_US
dspace.entity.type Publication
relation.isAuthorOfPublication 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isAuthorOfPublication.latestForDiscovery 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isOrgUnitOfPublication fd8e65fe-c3b3-4435-9682-6cccb638779c
relation.isOrgUnitOfPublication.latestForDiscovery fd8e65fe-c3b3-4435-9682-6cccb638779c

Files