Examples
TheHajnal–Szemerédi theorem
Brooks' theorem states that any connected graph with maximum degree Δ has a Δ-coloring, with two exceptions ( complete graphs and odd cycles). However, this coloring may in general be far from equitable. conjectured that an equitable coloring is possible with only one more color: any graph with maximum degree Δ has an equitable coloring with Δ + 1 colors. The case Δ = 2 is straightforward (any union of paths and cycles may be equitably colored by using a repeated pattern of three colors, with minor adjustments to the repetition when closing a cycle) and the case Δ + 1= ''n''/3 had previously been solved by . The full conjecture was proven by , and is now known as the Hajnal–Szemerédi theorem. Their original proof was long and complicated; a simpler proof was given by . A polynomial time algorithm for finding equitable colorings with this many colors was described by Kierstead and Kostochka; they credit Marcelo Mydlarz and Endre Szemerédi with a prior unpublished polynomial time algorithm. Kierstead and Kostochka also announce but do not prove a strengthening of the theorem, to show that an equitable ''k''-coloring exists whenever every two adjacent vertices have degrees adding to at most 2''k'' + 1. conjectured a form of Brooks' theorem for equitable coloring: every connected graph with maximum degree Δ has an equitable coloring with Δ or fewer colors, with the exceptions of complete graphs and odd cycles. A strengthened version of the conjecture states that each such graph has an equitable coloring with exactly Δ colors, with one additional exception, a complete bipartite graph in which both sides of the bipartition have the same odd number of vertices. proposed a strengthening of the Hajnal–Szemerédi theorem that also subsumes Dirac's theorem that dense graphs are Hamiltonian: he conjectured that, if every vertex in an ''n''-vertex graph has at least ''kn''/(''k'' + 1) neighbors, then the graph contains as a subgraph the graph formed by connecting vertices that are at most ''k'' steps apart in an ''n''-cycle. The case ''k'' = 1 is Dirac's theorem itself. The Hajnal–Szemerédi theorem may be recovered from this conjecture by applying the conjecture for larger values of ''k'' to the complement graph of a given graph, and using as color classes contiguous subsequences of vertices from the ''n''-cycle. Seymour's conjecture has been approximately proven, i.e. for graphs where every vertex has at least ''kn''/(''k'' + 1)+o(''n'') neighbors. The proof uses several deep tools including the Hajnal–Szemerédi theorem itself. Yet another generalization of the Hajnal–Szemerédi theorem is the Bollobás–Eldridge–Catlin conjecture (or BEC-conjecture for short). This states that if ''G''1 and ''G''2 are graphs on ''n'' vertices with maximum degree Δ1 and Δ2 respectively, and if (Δ1 + 1)(Δ2 + 1) ≤ ''n+1'', then ''G''1 and ''G''2 can be packed. That is, ''G''1 and ''G''2 can be represented on the same set of ''n'' vertices with no edges in common. The Hajnal–Szemerédi theorem is the special case of this conjecture in which ''G''2 is a disjoint union of cliques. provides a similar but stronger condition on Δ1 and Δ2 under which such a packing can be guaranteed to exist.Special classes of graphs
For any tree with maximum degree Δ, the equitable chromatic number is at most : with the worst case occurring for a star. However, most trees have significantly smaller equitable chromatic number: if a tree with ''n'' vertices has Δ ≤ ''n''/3 − O(1), then it has an equitable coloring with only three colors. studies the equitable chromatic number of graph products.Computational complexity
The problem of finding equitable colorings with as few colors as possible (below the Hajnal-Szemerédi bound) has also been studied. A straightforward reduction fromApplications
One motivation for equitable coloring suggested by 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. 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 (; ). 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.Notes
References
*. *. *. * *. * *. *. *. *. *. *. * *. *. *. *. {{refendExternal links