Equitable Coloring - Examples

Examples

The star K_1,5 shown in the illustration is a complete bipartite graph, and therefore may be colored with two colors. However, the resulting coloring has one vertex in one color class and five in another, and is therefore not equitable. The smallest number of colors in an equitable coloring of this graph is four, as shown in the illustration: the central vertex must be the only vertex in its color class, so the other five vertices must be split among at least three color classes in order to ensure that the other color classes all have at most two vertices. More generally, Meyer (1973) observes that any star K_1,n needs colors in any equitable coloring; thus, the chromatic number of a graph may differ from its equitable coloring number by a factor as large as n/4. Because K_1,5 has maximum degree five, the number of colors guaranteed for it by the Hajnal–Szemerédi theorem is six, achieved by giving each vertex a distinct color.

Another interesting phenomenon is exhibited by a different complete bipartite graph, K_{2n + 1,2n + 1}. This graph has an equitable 2-coloring, given by its bipartition. However, it does not have an equitable (2n + 1)-coloring: any equitable partition of the vertices into that many color classes would have to have exactly two vertices per class, but the two sides of the bipartition cannot each be partitioned into pairs because they have an odd number of vertices. Therefore, the equitable chromatic threshold of this graph is 2n + 2, significantly greater than its equitable chromatic number of two.