Dual Parameterization of Weighted Coloring.

Given a graph G, a properk-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 ∈ S i w (v) and the weight of a coloringc as w (c) = ∑ i = 1 k w (i) . Guan and Zhu (Inf Process Lett 61(2):77–81, 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 (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50–61, 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. [ABSTRACT FROM AUTHOR]