2026-04-14T07:48:45Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/3411442026-02-02T09:09:14Zcom_2072_1033col_2072_452950

On list k-coloring convex bipartite graphs Díaz Cort, Josep Yasar Diner, Oznur Serna Iglesias, María José Serra Albó, Oriol Universitat Politècnica de Catalunya. Departament de Ciències de la Computació Universitat Politècnica de Catalunya. Departament de Matemàtiques Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica Graph theory List coloring Convex bipartite Biconvex bipartite graphs Grafs, Teoria de List k–Coloring (LI k-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 LI k-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, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs. J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P. Peer Reviewed Postprint (author's final draft) 2020 Conference report Diaz, J. [et al.]. On list k-coloring convex bipartite graphs. A: Cologne-Twente Workshop on Graphs and Combinatorial Optimization. "Graphs and Combinatorial Optimization: from Theory to Applications: CTW2020 proceedingss". Berlín: Springer, 2020, p. 15-26. ISBN 978-3-030-63071-3. DOI 10.1007/978-3-030-63072-0_2. 978-3-030-63071-3 https://hdl.handle.net/2117/341144 10.1007/978-3-030-63072-0_2 eng https://link.springer.com/chapter/10.1007%2F978-3-030-63072-0_2 info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016/MTM2017-82166-P/ES/COMBINATORIA GEOMETRICA, ALGEBRAICA Y PROBABILISTICA/ info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016/TIN2017-86727-C2-1-R/ES/MODELOS Y METODOS BASADOS EN GRAFOS PARA LA COMPUTACION EN GRAN ESCALA/ info:eu-repo/grantAgreement/AGAUR/2017 SGR 786 Open Access 12 p. application/pdf Springer