Equitable Coloring - Applications

Applications

One motivation for equitable coloring suggested by Meyer (1973) concerns scheduling problems. In this application, the vertices of a graph represent a collection of tasks to be performed, and an edge connects two tasks that should not be performed at the same time. A coloring of this graph represents a partition of the tasks into subsets that may be performed simultaneously; thus, the number of colors in the coloring corresponds to the number of time steps required to perform the entire task. Due to load balancing considerations, it is desirable to perform equal or nearly-equal numbers of tasks in each time step, and this balancing is exactly what an equitable coloring achieves. Furmańczyk (2006) mentions a specific application of this type of scheduling problem, assigning university courses to time slots in a way that spreads the courses evenly among the available time slots and avoids scheduling incompatible pairs of courses at the same time as each other.

The Hajnal-Szemerédi theorem has also been used to bound the variance of sums of random variables with limited dependence (Pemmaraju 2001; Janson & Ruciński 2002). If (as in the setup for the Lovász local lemma) each variable depends on at most Δ others, an equitable coloring of the dependence graph may be used to partition the variables into independent subsets within which Chernoff bounds may be calculated, resulting in tighter overall bounds on the variance than if the partition were performed in a non-equitable way.