Dual parameterization of Weighted Coloring - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Dual parameterization of Weighted Coloring


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. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph (G, w) and an integer k, the question is whether σ(G, w) ≤ v∈V (G) w(v) − k. We prove that this problem is FPT by providing an algorithm running in time 9 k · n O(1) , and it is easy to see 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 we rule out the existence of polynomial kernels unless NP ⊆ coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
Fichier principal
Vignette du fichier
LIPIcs-IPEC-2018-12.pdf (544.65 Ko) Télécharger le fichier

Dates and versions

lirmm-02410739 , version 1 (13-12-2019)





Julio Araujo, Victor Campos, Carlos Vinícius G. C. Lima, Vinicius Fernandes dos Santos, Ignasi Sau, et al.. Dual parameterization of Weighted Coloring. IPEC 2018 - 13th International Symposium on Parameterized and Exact Computation, Aug 2018, Helsinki, Finland. pp.12:1--12:14, ⟨10.4230/LIPIcs.IPEC.2018.12⟩. ⟨lirmm-02410739⟩
57 View
114 Download



Gmail Facebook X LinkedIn More