Show simple item record

dc.contributor.authorDiaz, Josep
dc.contributor.authorDiner, Öznur Yaşar
dc.contributor.authorSerna, Maria
dc.contributor.authorOriol, Serra
dc.date.accessioned2021-07-17T17:27:20Z
dc.date.available2021-07-17T17:27:20Z
dc.date.issued2021
dc.identifier.issn25237047
dc.identifier.urihttps://hdl.handle.net/20.500.12469/4071
dc.description.abstractList 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.language.isoEnglishen_US
dc.publisherSpringer Natureen_US
dc.subjectBiconvex bipartite graphsen_US
dc.subjectConvex bipartiteen_US
dc.subjectList coloringen_US
dc.titleOn list k-coloring convex bipartite graphsen_US
dc.typeBook chapteren_US
dc.identifier.startpage15en_US
dc.identifier.endpage26en_US
dc.relation.journalAIRO Springer Seriesen_US
dc.identifier.volume5en_US
dc.identifier.doi10.1007/978-3-030-63072-0_2en_US
dc.contributor.khasauthorDiner, Özgür Yaşaren_US


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record