On lower bounds for the b-chromatic number of connected bipartite graphs

A b-coloring of a graph G by k colors is a proper k-coloring of the vertices of G such that in each color class there exists a vertex having neighbors in all the other k−1 color classes. The b-chromatic number χb(G) of a graph G is the largest integer k such that G admits a b-coloring by k colors. We present some lower bounds for the b-chromatic number of connected bipartite graphs. We also discuss some algorithmic consequences of such lower bounds on some subfamilies of connected bipartite graphs.