Investigating the bb-chromatic number of bipartite graphs by using the bicomplement

A bb-coloring of a graph GG by kk colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k−1k−1 color classes. The bb-chromatic number χb(G)χb(G) is the maximum integer kk for which GG has a bb-coloring by kk colors. For a bipartite graph G=(A∪B,E)G=(A∪B,E), the bicomplement of GG is the bipartite graph G˜=(A∪B,E˜) with E˜:={{a,b}∣a∈A,b∈B,{a,b}∉E}. In this paper, we investigate the bb-chromatic number for bipartite graphs with a special bicomplement. In particular, we consider graphs GG for which G˜ is disconnected or has maximum degree Δ(G˜)≤2. Moreover, we give partial answers to the question “Which dd-regular bipartite graphs GG satisfy χb(G)=d+1χb(G)=d+1?” and we show a Nordhaus–Gaddum-type result for GG and  G˜.