Skip to Main content Skip to Navigation
Conference papers

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. 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [35 references]  Display  Hide  Download
Contributor : Ignasi Sau <>
Submitted on : Friday, December 13, 2019 - 11:39:30 PM
Last modification on : Wednesday, June 24, 2020 - 10:48:04 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




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



Record views


Files downloads