On r-equitable colorings of bipartite graphs

Abstract

An r-equitable k-coloring of a graph G is a proper k-coloring of G so that the size of any two color classes differ by at most r. The least k such that G is r-equitably k-colorable is the r-equitable chromatic number of G. In this paper, we prove that the r-equitable chromatic number of a connected bipartite graph G(X, Y) with \X\ = m>n = |y| is at most + 1 provided that G satisfies a restriction on the number of edges. This generalizes a result of K.-W. Lih and P.-L. Wu [Discrete Math., 151 (1996) 155-160]. © 2015 Utilitas Mathematics.