EQUITABLE CHROMATIC NUMBER OF COMPLETE MULTIPARTITE GRAPHS

Dorothee Blum, Denise Torrey, and Richard Hammack

Abstract. The equitable chromatic number of a graph is the smallest integer n for which the graph’s vertex set can be partitioned into n independent sets, each pair of which differs in size by at most 1. We develop a formula and a linear–time algorithm which compute the equitable chromatic number of an arbitrary complete multipartite graph. These results yield tractable solutions of certain scheduling problems.

1. Introduction. A coloring of a graph G is an assignment of colors {1, 2, …, n} to the vertices V (G) of G with no two adjacent vertices having the same color. A coloring of G partitions its vertices into color classes V_{1}, V_{2}, …, V_{n}, where each V_{i} consists of the vertices that are colored with color i. An equitable coloring of G is a coloring of G with the additional property that −1 ≤ |V_{i}| − |V_{j}| ≤ 1 for each 1 ≤ i, j ≤ n. The equitable chromatic number of G, denoted χ_{e}(G), is the smallest integer n for which there is an equitable coloring of G with n colors.

Given positive integers p_{1}, p_{2}, …, p_{k}, the complete k–partite graph K(p_{1}, p_{2}, …, p_{k}) is the graph whose vertex set is the union P_{1} ∪P_{2} ∪⋯∪P_{k} of k partite sets, with each P_{i} consisting of p_{i} vertices, and with two vertices adjacent if and only if they belong to different partite sets. Complete k–partite graphs are also called complete multipartite graphs.

The ability to compute the equitable chromatic number of an arbitrary complete multipartite graph solves certain types of scheduling problems. Consider, for example, the following hypothetical situation: A mathematics department offers sections of Calculus I, Calculus II, and Calculus III. One semester 309 students wish to take Calculus I, 230 wish to take Calculus II, and 94 want to take Calculus III. In order to equalize the number of students that her professors must teach, the department chair wants no two sections to differ in size by more than 1, while the total number of sections is minimized. The required number of sections is χ_{e}(K(309, 230, 94)).

The equitable chromatic number of a graph was introduced by Meyer [7], and commented on in [8]. The definitive survey of the subject is by Lih [3]. Much recent activity in this area has centered on proving the Equitable Coloring Conjecture, which asserts χ_{e}(G) ≤ Δ(G), provided G is neither a complete graph nor an odd cycle, and where Δ(G) is the maximum vertex degree of G [3, 4, 5, 6]. Relatively little work has been done on finding explicit formulas for χ_{e}. Formulas for χ_{e}(G) are given in [2] for the cases in which G is a path, a cycle, a star, a wheel, or K_{n}. The derivations of these formulas are straightforward. Our article examines what is perhaps the simplest class of graphs for which computation of χ_{e} is nontrivial; namely, the complete multipartite graphs.

A formula which is superficially different from ours was established independently in a manuscript by Chen and Wu [1], and was reported in [3]; however, Chen and Wu never published their proof. To our knowledge, this article contains the only published proof. This work is based on the second author’s undergraduate honors thesis [2], which was directed by the first author.

2. Results. Before stating our main result, we need several preliminary results on integer partitions. Recall that a partition of an integer n is a sum of the form n = m_{1} + m_{2} + ⋯ + m_{k}, where 1 ≤ m_{i} ≤ n for each 1 ≤ i ≤ k. We call such a partition an x–partition if each m_{i} is in the set {x, x + 1}. An x–partition of n is typically denoted as n = ax + b(x + 1), where n is the sum of a x’s and b (x + 1)’s. An x–partition of n is called a minimal x–partition if the number of its addends, a + b, is as small as possible. For example, 2 + 2 + 2 + 2 is a 2–partition of 8, though it is not minimal, while 2 + 3 + 3 is a minimal 2–partition of 8.

Our first lemma states the conditions under which an x–partition of n exists. In what follows, all variables are nonnegative integers.

\underline{Lemma 1}. If 0 < x ≤ n, and n = px + r with 0 ≤ r < x, then there is an x–partition of n if and only if r ≤ p.

\underline{Proof}. If r ≤ p, then n = px + r = (p − r)x + r(x + 1) is an x–partition of n. Conversely, given an x–partition of ax + b(x + 1) of n, we have n = ax + b(x + 1) = (a + b)x + b, so a + b ≤ p and r ≤ b. Consequently, r ≤ b ≤ a + b ≤ p.

\underline{Corollary 1}. There is an x–partition of n if and only if n/(x + 1) ≤ ⌊n/x⌋.

\underline{Proof}. Using the division algorithm, write n = px + r with 0 ≤ r < x. Then p = ⌊n/x⌋, and r = n − ⌊n/x⌋x, and n − ⌊n/x⌋x ≤ ⌊n/x⌋ by Lemma 1. The Corollary follows immediately.

The next lemma gives conditions under which an x–partition of n is minimal.

\underline{Lemma 2}. An x–partition ax+b(x+1) of n is minimal if and only if a < x+1. Moreover, a minimal x–partition is unique.

\underline{Proof}. Regard a and b as variables, and x as fixed. Solving the linear relation n = ax + b(x + 1) for b yields a + b = (a + n)/(x + 1). Thus, a + b is a strictly increasing function of a, and, moreover, b decreases as a increases. Therefore, the x–partition n = ax + b(x + 1) will be minimal exactly when a is the smallest nonnegative integer for which (a + n)/(x + 1) is an integer. Once a is fixed, b is determined by the equation n = ax + b(x + 1). Uniqueness of minimal x–partitions follows.

Now suppose n = ax + b(x + 1) is an x–partition, and a < x + 1. By what was said in the previous paragraph, m = (a+n)/(x+1) is an integer. If the partition is not minimal then there are integers a′ and m′, with 0 ≤ a′ < a and 0 < m′ < m, for which m′ = (a′ + n)/(x + 1). Subtracting a′ + n = m′(x + 1) from a + n = m(x + 1) gives a − a′ = (m − m′)(x + 1), so a > a − a′ ≥ x + 1.

Conversely, if n = ax + b(x + 1) is a minimal x–partition of n, it is impossible for a ≥ x + 1, for otherwise n = ax + b(x + 1) = (a − (x + 1))x + (b + x)(x + 1) is an x–partition of n with a − (x + 1) + b + x = a + b − 1 addends, contradicting minimality. Thus, a < x + 1.

Now it is possible to describe exactly the number of addends in a minimal x–partition.

\underline{Lemma 3}. If n = ax + b(x + 1) is a minimal x–partition, then

a + b = ⌊\frac{n}{x}⌋ − ⌊⌊\frac{n}{x}⌋ − \frac{n}{x + 1}⌋ ,

b = n − x (⌊\frac{n}{x}⌋ − ⌊⌊\frac{n}{x}⌋ − \frac{n}{x + 1}⌋) ,

and a = \frac{n − b(x + 1)}{x}.

\underline{Proof}. Using the division algorithm, write n = px + r with 0 ≤ r < x, so p−r ≥ 0 by Lemma 1. Using the division algorithm again, write p−r = q(x+1)+s with 0 ≤ s < x+1. Now n = px+r = (p−r)x+r(x+1) = (q(x+1)+s)x+r(x+1) = sx+(qx+r)(x+1). By Lemma 2, sx+(qx+r)(x+1) is a minimal x–partition of n, so, by uniqueness, a = s and b = qx+r. Now, q = ⌊(p−r)/(x+1)⌋, p = ⌊n/x⌋, and r = n − ⌊n/x⌋x, so it follows that b = qx + r = n − x(⌊n/x⌋ − ⌊⌊n/x⌋ − n/(x + 1)⌋). Solving n = ax + b(x + 1) for a gives a = (n − b(x + 1))/x. Finally, substituting the expression for b into the expression for a, and adding the expressions for a and b gives a + b =⌊n/x⌋ − ⌊⌊n/x⌋ − n/(x + 1)⌋.

Let us set π(x, n) = ⌊n/x⌋ − ⌊⌊n/x⌋ − n/(x + 1)⌋, so that the previous lemma says a minimal x–partition of n has π(x, n) addends. It seems intuitively plausible that, as x increases, the number of addends in a minimal x–partition of n decreases. This is confirmed by the next lemma.

\underline{Lemma 4}. If there is an x–partition of n, and a y–partition of n, and x < y, then π(x, n) ≥ π(y, n).

\underline{Proof}. We show that π(x, n) − π(y, n) ≥ 0. Using the fact that ⌊r⌋ − ⌊s⌋ ≥ ⌊r − s⌋, it follows π(x, n) − π(y, n) = ⌊n/x⌋ − ⌊⌊n/x⌋ − n/(x + 1)⌋ − ⌊n/y⌋ + ⌊⌊n/y⌋ − n/(y + 1)⌋ ≥ ⌊n/(x + 1) − n/y⌋ + ⌊⌊n/y⌋ − n/(y + 1)⌋. The left–hand term is nonnegative because x < y, and the right–hand term is nonnegative by Corollary 1.

These results now combine to give a construction of a minimal equitable coloring of K(p_{1}, p_{2}, …, p_{k}). Denote the partite sets of the graph K(p_{1}, p_{2}, …, p_{k}) as P_{1}, P_{2}, …, P_{k}, with |P_{i}| = p_{i}. Any given color class of an equitable coloring must lie entirely in some P_{i}, for otherwise two of its vertices are adjacent. Thus, any equitable coloring partitions each P_{i} into color classes V_{i1}, V_{i2}, …, V_{iv_{i}}, no two of which differ in size by more than 1. If the sizes of the color classes are in the set {x, x + 1}, then these sizes induce x–partitions of each p_{i}. Conversely, given a number x and x–partitions p_{i} = a_{i}x + b_{i}(x + 1), of each p_{i}, there is an equitable coloring of K(p_{1}, p_{2}, …, p_{k}) with color classes of sizes x and x + 1; just partition each P_{i} into a_{i} sets of size x, and b_{i} sets of size x + 1. It follows, then, that finding an equitable coloring of K(p_{1}, p_{2}, …, p_{k}) amounts to finding a number x, and simultaneous x–partitions of each of the numbers p_{i}. By Corollary 1, a necessary condition for x is that p_{i}/(x + 1) ≤ ⌊p_{i}/x⌋ for all 1 ≤ i ≤ k. Certainly such an x exists, because x = 1 does the trick.

If we want the coloring to be minimal, x must be chosen with the additional property that the total number of color classes is as small as possible. According to Lemmas 3 and 4, it suffices to choose the largest x for which p_{i}/(x + 1) ≤ ⌊p_{i}/x⌋, 1 ≤ i ≤ k, and partition each P_{i} into π(x, p_{i}) color classes, b_{i} = n − x(⌊p_{i}/x⌋ − ⌊⌊p_{i}/x⌋ − p_{i}/(x + 1)⌋) of size x + 1, and a_{i} = (p_{i} − b_{i}(x + 1))/x of size x. This proves the following.

\underline{Theorem 1}. Denote the partite sets of K(p_{1}, p_{2}, …, p_{k}) as P_{1}, P_{2}, …, P_{k}, with |P_{i}| = p_{i}, and set x = max{x ∈ ℕ | p_{i}/(x + 1) ≤ ⌊p_{i}/x⌋, 1 ≤ i ≤ k}. Then

χ_{e}(K(p_{1}, p_{2}, …, p_{k})) = ∑_{i=1}^{k} (⌊\frac{p_{i}}{x} ⌋ − ⌊⌊\frac{p_{i}}{x} ⌋ − \frac{p_{i}}{x + 1}⌋) .

Moreover, a minimal equitable coloring is obtained by partitioning each P_{i} into b_{i} = n − x(⌊p_{i}/x⌋ − ⌊⌊p_{i}/x⌋ − p_{i}/(x + 1)⌋) color classes of size x + 1, and a_{i} = (p_{i} − b_{i}(x + 1))/x color classes of size x.

Theorem 1 leads immediately to an algorithm which finds a minimal equitable coloring of K(p_{1}, p_{2}, …, p_{k}). The algorithm first finds the largest x for which p_{i}/(x + 1) ≤ ⌊p_{i}/x⌋ for all 1 ≤ i ≤ k, then computes the sizes of the color classes according to Theorem 1. Now, no color class can be larger than M = min({p_{1}, p_{2}, …, p_{k}}), so x cannot be larger than this number. The algorithm operates by first setting x = M, then decrementing x until p_{i}/(x + 1) ≤ ⌊p_{i}/x⌋ for all 1 ≤ i ≤ k. This guarantees that x will be as stated in Theorem 1.

\underline{Algorithm 1}. Find a minimal equitable coloring of K(p_{1}, p_{2}, …, p_{k}).

begin

M := min({p_{1}, p_{2}, …, p_{k}})
x := M + 1
success := 0
while (success = 0)

x := x − 1 success := 1 for i := 1 to k

if ( p_{i}/(x + 1) > ⌊ p_{i}/x ⌋ ) success := 0

end (for) end (while) N := 0 for i := 1 to k

b_{i} := p_{i} − x (⌊\frac{p_{i}}{x} ⌋ − ⌊⌊\frac{p_{i}}{x} ⌋ − \frac{p_{i}}{x + 1}⌋)

a_{i} := \frac{p_{i} − b_{i}(x + 1)}{x}

N := N + a_{i} + b_{i} end (for)

The equitable chromatic number of K(p_{1}, p_{2}, …, p_{k}) is N.

A minimal equitable coloring is obtained by partitioning the partite set P_{i} into

a_{i} color classes of size x and b_{i} color classes of size x + 1, 1 ≤ i ≤ k.

end (Algorithm 1).

Notice that the algorithm terminates, for the while loop stops – in the worst case – when x finally reaches the value of 1. The complexity of the algorithm is linear in p = |V (K(p_{1}, p_{2}, …, p_{k}))|, for, in the worst case, the while loop executes M(2 + k) ≤ 3p steps, and the second for loop executes 3k ≤ 3p steps.

\underline{References}

1 B.–L. Chen and C.–H. Wu, “The Equitable Coloring of Complete Partite Graphs,” manuscript, 1994.

2 D. Grittner, The Equitable Chromatic Number for a Complete Bipartite Graph, Undergraduate honors thesis, Millersville University, Millersville, PA, 1995.

3 K.–W. Lih, “The Equitable Coloring of Graphs,” Handbook of Combinatorial Optimization, Vol. 3, Kluwer Academic Publishers, Boston, MA, 1998.

4 K.–W. Lih, P.–L. Wu, “On Equitable Coloring of Bipartite Graphs,” Discrete Mathematics, 151 (1996), 155–160.

5 B.–L. Chen, K.–W. Lih, “Equitable Coloring of Trees,” Journal of Combinatorial Theory, Series B, 61 (1994), 83–87.

6 B.–L. Chen, K.–W. Lih, P.–L. Wu, “Equitable Coloring and the Maximum Degree,” European Journal of Combinatorics, 15 (1994), 443–447.

7 W. Meyer, “Equitable coloring,” American Mathematical Monthly, 80 (1973), 920–922.

8 T. Jensen and B. Toft, Graph Coloring Problems, Wiley Interscience, New York, NY, 1995.

Dorothee Blum Department of Mathematics Millersville University Millersville, PA 17551 email: dblum@marauder.millersville.edu

Denise Torrey Navy Mutual Aid Association Arlington, VA 22212 email: datorrey@erols.com

Richard Hammack Department of Mathematics Randolph–Macon College Ashland, VA 23005 email: rhammack@rmc.edu