2026-07-25T06:40:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11880 2024-03-06T10:48:55Z ddc:004 open_access

Parameterized Pre-Coloring Extension and List Coloring Problems Gutin, Gregory Majumdar, Diptapriyo Ordyniak, Sebastian Wahlström, Magnus Parameterized Algorithms W-hardness Kernelization Graph Coloring List Coloring Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of vertices, whose removal results in a clique) of size k for G, and a list L(v) of colors for every v ∈ V(G), decide whether G has a proper list coloring; (2) Given a graph G, a clique modulator D of size k for G, and a pre-coloring λ_P: X → Q for X ⊆ V(G), decide whether λ_P can be extended to a proper coloring of G using only colors from Q. For Problem 1 we design an O*(2^k)-time randomized algorithm and for Problem 2 we obtain a kernel with at most 3k vertices. Banik et al. (IWOCA 2019) proved the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph G, an integer k, and a list L(v) of exactly n-k colors for every v ∈ V(G), decide whether there is a proper list coloring for G. We obtain a kernel with O(k²) vertices and colors and a compression to a variation of the problem with O(k) vertices and O(k²) colors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gregory Gutin and Diptapriyo Majumdar and Sebastian Ordyniak and Magnus Wahlström 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.19 urn:nbn:de:0030-drops-118801 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.19 eng https://creativecommons.org/licenses/by/3.0/legalcode