Skip to Main content Skip to Navigation
Journal articles

Dual Parameterization of Weighted Coloring

Abstract : Given a graph G, a proper k-coloring of G is a partition c = (S i) i∈[1,k] of V (G) into k stable sets S 1 ,. .. , S k. Given a weight function w : V (G) → R + , the weight of a color S i is defined as w(i) = max v∈Si w(v) and the weight of a coloring c as w(c) = k i=1 w(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G, w), denoted by σ(G, w), as the minimum weight of a proper coloring of G. The problem of determining σ(G, w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time n o(log n) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is σ(G, w) ≤ v∈V (G) w(v) − k? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time 2 O(k log k) · n O(1) , and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time 9 k ·n O(1) , and prove that no algorithm in time 2 o(k) ·n O(1) exists under the ETH. On the other hand, we present a kernel with at most (2 k−1 + 1)(k − 1) vertices, and rule out the existence of polynomial kernels unless NP ⊆ coNP/poly, even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
Document type :
Journal articles
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Ignasi Sau <>
Submitted on : Thursday, November 5, 2020 - 12:25:54 PM
Last modification on : Friday, November 6, 2020 - 4:56:49 AM
Long-term archiving on: : Saturday, February 6, 2021 - 7:11:45 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Júlio Araújo, Victor Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau Valls, et al.. Dual Parameterization of Weighted Coloring. Algorithmica, Springer Verlag, 2020, 82 (8), pp.2316-2336. ⟨10.1007/s00453-020-00686-7⟩. ⟨lirmm-02989870⟩



Record views


Files downloads