Structural Parameterizations of Budgeted Graph Coloring
share
We introduce a variant of the graph coloring problem, which we denote as Budgeted Coloring Problem (). Given a graph G, an integer c and an ordered list of integers {b_1, b_2, …, b_c}, asks whether there exists a proper coloring of G where the i-th color is used to color at most b_i many vertices. This problem generalizes two well-studied graph coloring problems, Bounded Coloring Problem () and Equitable Coloring Problem () and as in the case of other coloring problems, it is even for constant values of c. So we study under the paradigm of parameterized complexity. * We show that is (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for and immediately extends to the , which was earlier not known. * We show that is polynomial time solvable for cluster graphs generalizing a similar result for . However, we show that is , but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for for the same parameter. * While the is known to be polynomial time solvable on split graphs, we show that is on split graphs. As is hard on bipartite graphs when c>3, the result follows for as well. We provide a dichotomy result by showing that is polynomial time solvable on bipartite graphs when c=2. We also show that is on co-cluster graphs, contrasting the polynomial time algorithm for and . Finally we present an 𝒪^*(2^|V(G)|) algorithm for the , generalizing the known algorithm with a similar bound for the standard chromatic number.
READ FULL TEXT