On equitable coloring of bipartite graphs (Q1916388): Difference between revisions

The equitable chromatic number \(\chi_e (G)\) of a graph \(G\) is the smallest integer \(k\) such that the vertex-set of \(G\) can be partitioned into \(k\) independent sets \(V_1, \dots, V_k\) with \(|V_i |- 1 \leq |V_j |\leq |V_i |+ 1\) for any two indices \(i\) and \(j\) (i.e. there exists a proper vertex-colouring of \(G\) with exactly \(k\) colours such that all colour-classes have almost the same size). Brooks' theorem states that the usual chromatic number \(\chi (G)\) of \(G\) is at most the maximal degree \(\Delta (G)\) in \(G\) for all connected graphs \(G\) except the complete graphs and the odd cycles. The equitable colouring conjecture asserts that even \(\chi_e (G) \leq \Delta (G)\) holds for all such graphs. In the present paper, the authors verify this conjecture for all connected bipartite graphs \(G\). Moreover, they prove that \(\chi_e (G) \leq \lceil m/(n + 1) \rceil + 1\) if there exists a bipartition \((X,Y)\) of \(G\) such that \(|X |= m \geq |Y |= n\) and \(G\) has less than \(\lfloor m/(n + 1) \rfloor (m - n) + 2m\) edges.