Equitable colorings of line graphs and complete \(r\)-partite graphs (Q2721926)

Let \(G(V,E)\) be a simple graph. The graph \(G\) is said to be equitably \(k\)-colorable if the vertex set \(V\) can be partitioned into \(k\) independent sets \(V_1,V_2, \ldots, V_k\) such that \(||V_i|-|V_j||\leq 1\) for all \(i\) and \(j\). The smallest integer \(k\) to make such a partition possible is called the equitable chromatic number of \(G\) and is denoted by \(\chi_{_=}(G)\). If \(G\) is a connected graph with the maximum degree \(\Delta(G)\), Meyer conjectured that \(\chi_{_=}(G) \leq \Delta(G)\) except \(G\) is a complete graph or an odd cycle. It is proved in this paper that Meyer's conjecture is true for line graphs and complete \(r\)-partite graphs.