On the parameterized complexity of b-chromatic number

Abstract

The b-chromatic number of a graph G, ź b ( G ) , is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b-Chromatic Number problem, the objective is to decide whether ź b ( G ) ź k . Testing whether ź b ( G ) = Δ ( G ) + 1 , where Δ ( G ) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvíl, Tuza and Voigt, WG 2002). We show that b-Chromatic Number is W1-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k = Δ ( G ) + 1 , we design an algorithm for b-Chromatic Number running in time 2 O ( k 2 log ź k ) n O ( 1 ) . Finally, we show that b-Chromatic Number for an n-vertex graph can be solved in time O ( 3 n n 4 log ź n ) . We show that b-Chromatic Number is W1-hard when parameterized by the b-chromatic number, k.When k = Δ ( G ) + 1 , an algorithm of running in 2 O ( k 2 log ź k ) n O ( 1 ) is provided.An O ( 3 n n 4 log ź n ) time algorithm on an n-vertex graph is provided.