Equitable chromatic number of complete multipartite graphs (Q1407486): Difference between revisions

An equitable \(n\)-coloring of a graph \(G\) is a proper \(n\)-coloring of \(G\) such that the color classes \(V_i\) satisfy the condition \(||V_i|-|V_j||\leq 1\) for all \(i,j\) with \(1 \leq i\), \(j \leq n\). The equitable chromatic number \(\chi_e(G)\) is the smallest integer \(n\) such that \(G\) can be equitably colored with \(n\) colors. Given positive integers \(p_1, p_2, \dots , p_k\), the complete \(k\)-partite graph \(K(p_1, p_2, \dots , p_k)\) is the graph whose vertex set is the union \(P_1 \cup P_2 \cup \cdots \cup P_k\) of \(k\) partite sets, each \(P_i\) consists of \(p_i\) vertices, and two vertices are adjacent if and only if they belong to different partite sets. The main theorem of this paper says that \(\chi_e(K(p_1, p_2, \dots , p_k))=\sum_{i=1}^k(\lfloor p_i/x \rfloor - \lfloor \lfloor p_i/x \rfloor - p_i/(x+1) \rfloor)\), where \(x\) is the largest integer satisfying \(p_i/(x+1) \leq \lfloor p_i/x \rfloor\) for each \(i\) with \(1 \leq i \leq k\).