Given a bipartite graph G (U∪ V, E) with n vertices on each side, an independent set I∈ G such that| U∩ I|=| V∩ I| is called a balanced bipartite independent set. A balanced coloring of G is a coloring of the vertices of G such that each color class induces a balanced bipartite independent set in G. If graph G has a balanced coloring we call it colorable. The coloring number χB (G) is the minimum number of colors in a balanced coloring of a colorable graph G. We shall give bounds on χB (G) in terms of the average degree article amssymb amsbsy\usepackage mathscr euscript\footskip= 0pc empty ̄d of G and in terms of the maximum degree Δ of G. In particular we prove the following: article amssymb amsbsy\usepackage mathscr euscript\footskip= 0pc empty B(G)≦max{2,⌊2d1\}. For any 0< ε< 1 there is a constant Δ0 such that the following holds. Let G be a balanced bipartite graph with maximum degree Δ≥ Δ0 and n≥(1+ ε) 2Δ vertices on each side, then article amssymb amsbsy\usepackage mathscr euscript\footskip= 0pc empty B(G)≦20ϵ^2Δln\,Δ.© 2009 Wiley Periodicals, Inc. J Graph Theory 64: 277–291, 2010