Parameterized and Approximation Algorithms for the Load Coloring Problem

Let c, k be two positive integers. Given a graph $G=(V,E)$ , the c‐Load Coloring problem asks whether there is a c‐coloring $\mathit{\phi }:V\to [c]$ such that for every $i\in [c]$ , there are at least k edges with both endvertices colored i. Gutin and Jones (Inf Process Lett 114:446–449, 2014) studied this problem with $c=2$ . They showed 2‐Load Coloring to be fixed‐parameter tractable (FPT) with parameter k by obtaining a kernel with at most 7k vertices. In this paper, we extend the study to any fixed c by giving both a linear‐vertex and a linear‐edge kernel. In the particular case of $c=2$ , we obtain a kernel with less than 4k vertices and less than $6k+(3+\sqrt{2})\sqrt{k}+4$ edges. These results imply that for any fixed $c\ge 2$ , c‐Load Coloring is FPT and the optimization version of c‐Load Coloring (where k is to be maximized) has an approximation algorithm with a constant ratio.