Equitable Coloring of Graphs

Abstract

If the vertices of a graph G are colored with k colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then G is said to be equitably k-colorable. The equitable chromatic number $\chi _{_{=}}(G)$ is the smallest integer k such that G is equitably k-colorable. In the first introduction section, results obtained about the equitable chromatic number before 1990 are surveyed. The research on equitable coloring has attracted enough attention only since the early 1990s. In the subsequent sections, positive evidence for the important equitable Δ-coloring conjecture is supplied from graph classes such as forests, split graphs, outerplanar graphs, series-parallel graphs, planar graphs, graphs with low degeneracy, graphs with bounded treewidth, Kneser graphs, and interval graphs. Then three kinds of graph products are investigated. A list version of equitable coloring is introduced. The equitable coloring is further examined in the wider context of graph packing. Appropriate conjectures for equitable Δ-coloring of disconnected graphs are then studied. Variants of the well-known and significant Hajnal and Szemerédi Theorem are discussed. A brief summary of applications of equitable coloring is given. Related notions, such as equitable edge coloring, equitable total coloring, equitable defective coloring, and equitable coloring of uniform hypergraphs, are touched upon. This chapter ends with a short conclusion section. This survey is an updated version of Lih [102].

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A graph G consists of a vertex set V (G) and an edge set E(G). All graphs considered in this chapter are finite, loopless, and without multiple edges. Let | G | and ∥ G ∥ denote the number of vertices, also known as the order, and the number of edges of the graph G, respectively. If the vertices of a graph G can be partitioned into k sets V ₁, V ₂, …, V _k such that each V _i is an independent set (none of its vertices are adjacent), then G is said to be k-colorable and the k sets are called its color classes. Equivalently, a coloring can be viewed as a function π : V (G) → { 1, 2, …, k} such that adjacent vertices are mapped to distinct numbers. The mapping π is said to be a (proper) k-coloring. All pre-images of a fixed i, 1 ≤ i ≤ k, form a color class. The smallest number k, denoted by χ(G), such that G is k-colorable is called the chromatic number of G. The graph G is said to be equitably colored with k colors, or equitably k-colorable, if there is a k-coloring whose color classes satisfy the condition $\vert \vert V _{i}\vert -\vert V _{j}\vert \vert \leq 1$ for every pair V _i and V _j . The smallest integer k for which G is equitably k-colorable, denoted by $\chi _{_{ =}}(G)$, is called the equitable chromatic number of G. Suppose that the graph G of order n is equitably colored with k colors. If n = qk + r, where 0 ≤ r < k, then there are exactly r color classes of size q + 1 and exactly k − r color classes of size q. The sizes of the color classes can be enumerated as $\lfloor n/k\rfloor,\lfloor (n + 1)/k\rfloor,\cdots \,,\lfloor (n + k - 1)/k\rfloor$ in a nondecreasing order. Note that $\lfloor (n + t - 1)/k\rfloor = \lceil (n + t - k)/k\rceil$ for 1 ≤ t ≤ k.

The notion of an equitable coloring was first introduced in [115] by W. Meyer. His motivation came from Tucker’s paper [138], in which vertices represent garbage collection routes and two such vertices are adjacent when the corresponding routes should not be run on the same day. Meyer thought that it would be desirable to have an approximately equal number of routes run on each of the 6 days in a week.

Let deg _G (v), or deg(v) for short, denote the degree of the vertex v in the graph G and $\Delta (G) =\max \{\deg (v)\mid v \in V (G)\}$. Let ⌈x⌉ and ⌊x⌋ denote, respectively, the smallest integer not less than x and the largest integer not greater than x. The main result obtained by Meyer was that a tree T can be equitably colored with $\lceil \Delta (T)/2\rceil + 1$ colors. However, there were gaps in his proof. According to Guy’s report [63], Eggleton could extend Meyer’s result to show that a tree T can be equitably colored with k colors, provided $k \geq \lceil \Delta (T)/2\rceil + 1$. A finer result about trees is the following theorem by Bollobás and Guy [16].

Theorem 1

A tree T is equitably 3-colorable if $\vert T\vert \geq 3\Delta (T) - 8$ or |T| = 3Δ(T) − 10.

The most interesting contribution made in Meyer’s paper is to propose the following conjecture. It is also called the Equitable Coloring Conjecture (ECC). Let K _n and C _n denote, respectively, a complete graph and a cycle on n vertices.

Conjecture 1

Let G be a connected graph. If G is neither a complete graph K _n nor an odd cycle $c_{2n + 1}$, then $\chi _{_{=}}(G) \leq \Delta (G)$.

Meyer was successful in verifying the ECC only for graphs with six or fewer vertices. Apparently the motivation of the ECC came from the following fundamental Brooks’ Theorem [19].

Theorem 2

Let G be a connected graph. If G is neither a complete graph K _n nor an odd cycle C _2n+1, then $\chi (G) \leq \Delta (G)$.

The well-known Hajnal and Szemerédi Theorem [64], when rephrased in terms of equitable colorings, had already shown the following before Meyer’s paper.

Theorem 3

A graph G (not necessarily connected) is equitably k-colorable if k ≥ Δ(G) + 1.

Let $\chi _{_{=}}^{{\ast}}(G)$ denote the smallest integer n such that G is equitably k-colorable for all k ≥ n. Then an equivalent formulation of Theorem 3 is that $\chi _{_{ =}}^{{\ast}}(G) \leq \Delta (G) + 1$ holds for any graph G. There is a notable contrast between the equitable colorability and the ordinary colorability: $\chi _{_{ =}}^{{\ast}}(G)$ may in fact be greater than $\chi _{_{=}}(G)$. This will be demonstrated later. Therefore, it makes sense to introduce the notion $\chi _{_{ =}}^{{\ast}}(G)$, and it shall be called the equitable chromatic threshold of G.

In an entirely different context, de Werra [39] treated color sequences and the majorization order among them. His results have consequences in equitable colorability. A sequence of nonnegative integers h = (h ₁, h ₂, …, h _k ) is called a color sequence for a given graph G if the following conditions hold:

• 1. h ₁ ≥ h ₂ ≥ ⋯ ≥ h _k ≥ 0.

• 2. There is a k-coloring of G such that the color classes V ₁, V ₂, …, V _k satisfy | V _i | = h _i for 1 ≤ i ≤ k.

The majorization order, also known as the dominance order, is a widely used notion in measuring the evenness of distributions. Marshall and Olkin [110] offer a comprehensive treatment of majorization. Let $\alpha : a_{1} \geq a_{2} \geq \cdots \geq a_{k} \geq 0$ and $\beta : b_{1} \geq b_{2} \geq \cdots \geq b_{k} \geq 0$ be two sequences of nonnegative integers. The sequence α is said to be majorized by the sequence β if the following two conditions hold:

• 1. $\sum _{i=1}^{j}a_{i} \leq \sum _{i=1}^{j}b_{i}$ for any j, 1 ≤ j < k.

• 2. $\sum _{i=1}^{k}a_{i} =\sum _{ i=1}^{k}b_{i}$.

Let K _{m, n} denote the complete bipartite graph whose parts are of size m and size n, respectively. A claw-free graph is a graph containing no K _{1, 3} as an induced subgraph. One of de Werra’s results is the following:

Theorem 4

Let G be a claw-free graph and h = (h ₁ ,h ₂ ,…,h _k ) be a color sequence of G. Then any sequence of nonnegative integers $h^{\prime} = (h_{1}^{\prime},h_{2}^{\prime},\ldots,h_{k}^{\prime})$ is also a color sequence if h′ is majorized by h.

Combining Theorems 2 and 4, it follows that, for a claw-free graph G, G is equitably k-colorable for all k ≥ χ(G), or equivalently $\chi _{_{=}}^{{\ast}}(G) =\chi _{_{=}}(G) =\chi (G)$. Although this fact can be shown directly, it was first implicitly implied in de Werra’s paper. It follows immediately that the ECC holds for claw-free graphs. Since every line graph is claw-free, the ECC holds for line graphs in particular. This was also obtained in Wang and Zhang [149].

This ends the history of pre-1990 activities on the equitable coloring of graphs.

2 Bipartite Graphs

A graph is called r-partite if its vertex set can be partitioned into r-independent sets V ₁, V ₂, …, V _r and complete r-partite, denoted by $K_{n_{1},n_{2},\ldots,n_{r}}$, if every vertex in V _i is adjacent to every vertex in V _j whenever i≠j and $\vert V _{i}\vert = n_{i} \geq 1$ for every 1 ≤ i ≤ r. By convention it is always assumed that r ≥ 2 and $1 \leq n_{1} \leq n_{2} \leq \cdots \leq \ n_{r}$. A graph is said to be complete multipartite if it is complete r-partite for some r. A bipartite graph is synonymous with a 2-partite graph. Let I _n denote the graph consisting of n isolated vertices. Then I _n is equitably k-colorable with color classes of size ⌊x⌋ or ⌈x⌉ if and only if $\lfloor x\rfloor \leq \lfloor n/k\rfloor \leq \lceil n/k\rceil \leq \lceil x\rceil$ or, equivalently, if and only if $\lceil n/\lceil x\rceil \rceil \leq k \leq \lfloor n/\lfloor x\rfloor \rfloor$.

Lih and Wu [102] first settled the ECC for bipartite graphs.

Theorem 5

If a connected bipartite graph G is different from any complete bipartite graph K _n,n, then G can be equitably colored with Δ(G) colors.

Theorem 6

The complete bipartite graph K _n,n can be equitably colored with k colors if and only if $\lceil n/\lfloor k/2\rfloor \rceil -\lfloor n/\lceil k/2\rceil \rfloor \leq 1$.

The proof for the complete bipartite case is straightforward by considering the appropriate sizes of the color classes. One interesting point to note is that, for k = n = Δ(K _{n, n} ), the difference involved in Theorem 6 is 0 when n is even and is 2 when n is odd. In view of Theorem 5, one can conclude that, except the complete bipartite graphs K _{2m + 1, 2m + 1}, every connected bipartite graph G can be equitably colored with Δ(G) colors. Clearly, $\chi (K_{2m+1,2m+1}) =\chi _{_{=}}(K_{2m+1,2m+1}) = 2$, yet $\chi _{_{=}}^{{\ast}}(K_{2m+1,2m+1}) = 2m + 2$. There is a gap between the equitable chromatic number and the equitable chromatic threshold. Nevertheless, ECC holds for connected bipartite graphs.

In many cases, the equitable chromatic number is below the maximum degree. If additional constraints are imposed upon the graph, a better bound for the equitable chromatic number could be obtained. The following is a result of this type:

Theorem 7

Let G = G(X,Y ) be a connected bipartite graph with two parts X and Y such that ∥G∥ = e. Suppose |X| = m ≥ n = |Y | and e < ⌊m∕(n + 1)⌋ (m − n) + 2m. Then $\chi _{_{=}}(G) \leq \lceil m/(n + 1)\rceil + 1$.

The bound for the equitable chromatic number in the above theorem is indeed better than Δ(G) when there are at least two edges. The following conjecture was made by B.-L. Chen in a personal communication:

Conjecture 2

Let G be a connected bipartite graph. Then $\chi _{_{=}}(G) \leq \lceil \Delta (G)/2\rceil + 1$.

Chen proved its validity when the maximum degree is at least 53. It is also trivial to see that the conjecture holds for complete bipartite graphs. The Meyer-Eggleton result about trees gives another positive evidence.

Wang and Zhang [149] established the validity of ECC for complete multipartite graphs. The exact value of the equitable chromatic number of a complete multipartite graph $K_{n_{1},n_{2},\ldots,n_{r}}$ was determined by Lam et al. [99].

Theorem 8

Let M be the largest natural number such that $n_{i}\ (\mathrm{mod}\ M) < \lceil n_{i}/M\rceil$ for $1 \leq i \leq r$. Then $\chi _{_{=}}(K_{n_{1},n_{2},\ldots,n_{r}}) =\sum _{ i=1}^{r}\left \lceil n_{i}/(M + 1)\right \rceil$.

Blum et al. [12] also obtained a formula for $\chi _{_{ =}}(K_{n_{1},n_{2},\ldots,n_{r}})$. For r ≥ 2, let K _r(n) denote the complete multipartite graph $K\mathop{\underbrace{{n,n\ldots,n}}}\limits _{r}$. Theorem 6 has been generalized to K _r(n) in [104].

Theorem 9

Let integers n ≥ 1 and k ≥ r ≥ 2. Then K _r(n) is equitably k-colorable if and only if $\left \lceil \frac{n} {\left \lfloor k/r\right \rfloor }\right \rceil -\left \lfloor \frac{n} {\left \lceil k/r\right \rceil }\right \rfloor \leq 1$.

Complete multipartite graphs also furnish us with examples to show thatthe inequalities $\chi (G) \leq \chi _{_{=}}(G) \leq \chi _{_{=}}^{{\ast}}(G)$ can be strict. For instance [103], let $G_{1} = K\mathop{\underbrace{{1,1,\ldots,1}}}\limits_{m} {,2n+1}$, $G_{2} = K\mathop{\underbrace{{2n+1,2n+1,\ldots,2n+1}}}\limits _{m}$, and $G_{3} = K_{2n+1,2n+1,}\mathop{\underbrace{{4n+2,4n+2,\ldots,4n+2}}}\limits _{m}$. Then

• 1. $\chi (G_{1}) = m + 1 <\chi _{_{=}}(G_{1}) =\chi _{ _{=}}^{{\ast}}(G_{1}) = m + n + 1$.

• 2. $\chi (G_{2}) =\chi _{_{=}}(G_{2}) = m <\chi _{ _{=}}^{{\ast}}(G_{2}) = m(n + 1)$.

• 3. $\chi (G_{3}) = m + 2 <\chi _{_{=}}(G_{3}) = 2(m + 1) <\chi _{ _{=}}^{{\ast}}(G_{3}) = (m + 1)(2n + 1) + 1$.

As to the gap between the chromatic number and the equitable chromatic number, Wang and Zhang [149] proposed the following:

Conjecture 3

For any graph G, $\chi _{_{ =}}(G) -\chi (G) \leq \lfloor \Delta (G)/2\rfloor$.

The upper bound is sharp in the sense that it can be attained by a star K _{1, 2n + 1}.

3 Trees

A graph is said to be nontrivial if it contains at least one edge. There is a natural way to regard a nontrivial tree T as a bipartite graph T(X, Y ). The technique used to prove the ECC for connected bipartite graphs can be applied to find the equitable chromatic number of a nontrivial tree when the sizes of the two parts differ by at most one. First try to cut the parts into classes of nearly equal size. If there are vertices remaining, then one can manage to find nonadjacent vertices in the opposite part to form a class of the right size. The following was established in Chen and Lih [26].

Theorem 10

Let T = T(X,Y ) be a nontrivial tree satisfying $\vert \vert X\vert -\vert Y \vert \vert \leq 1$. Then $\chi _{_{=}}(T) =\chi _{ _{=}}^{{\ast}}(T) = 2$.

When the sizes of the two parts differ by more than one, the determination in [26] for the equitable chromatic number of a tree needs extra notation. For any vertex u of a graph G, an independent set containing u is called a u-independent set. Let α _u (G)n denote the maximum size of a u-independent set in G.

Now suppose that G is partitioned into $\chi _{_{=}}(G)$ parts of independent sets. Let v be an arbitrary vertex of G. Then the part containing v has size at most α _v (G), and other parts have size at most α _v (G) + 1. It follows that $\vert G\vert \leq \alpha _{v}(G) + (\chi _{_{=}}(G) - 1)$ $(\alpha _{v}(G) + 1) =\chi _{_{=}}(G)(\alpha _{v}(G) + 1) - 1$.

Lemma 1

Let v be an arbitrary vertex of G, then $\chi _{_{=}}(G) \geq \lceil (\vert G\vert + 1)/(\alpha _{v}(G) + 1)\rceil$.

An induction based on Theorem 1 leads to the following:

Theorem 11

Let T = T(X,Y ) be a tree satisfying ||X|−|Y || > 1. Then $\chi _{_{=}}(T) =\chi _{ _{=}}^{{\ast}}(T) =\max \{ 3,\lceil (\vert T\vert + 1)/(\alpha _{u}(T) + 1)\rceil \}$, where u is an arbitrary vertex of maximum degree in T.

The following result was proved by Miyata et al. in an unpublished manuscript [116] without using Theorem 1:

Theorem 12

Let T be a tree and k ≥ 3 be an integer. Then T is equitably k-colorable if and only if $k \geq \max _{v\in V (T)}\left \lceil (\vert T\vert + 1)/(\alpha _{v}(T) + 1)\right \rceil$.

The inequality in the above theorem can be equivalently described as $\alpha _{v}(T) \geq \lfloor \vert T\vert /k\rfloor$ for any vertex v of T. This can be seen from the following equivalences which hold for any integer k and graph G:

$$\displaystyle\begin{array}{rcl} k& \geq & \left \lceil \frac{\vert G\vert + 1} {\alpha _{v}(G) + 1}\right \rceil \Leftrightarrow k \geq \frac{\vert G\vert + 1} {\alpha _{v}(G) + 1} \Leftrightarrow \alpha _{v}(G) \geq \frac{\vert G\vert - k + 1} {k} \Leftrightarrow \alpha _{v}(G) \\ & \geq & \left \lfloor \frac{\vert G\vert } {k} \right \rfloor. \end{array}$$

Actually, the difference between characterizations in [26] and [116] is only apparent. In view of the following lemma, Chang [22] gave a simplified and unified proof for the more general case of a forest:

Lemma 2

Let u be a vertex of a forest F. If $\lceil (\vert F\vert + 1)/(\alpha _{u}(F) + 1)\rceil> 3$, then u is the unique vertex of maximum degree in F.

Theorem 13

Let F be a forest and k ≥ 3 be an integer. Then F is equitably k-colorable if and only is $\alpha _{v}(F) \geq \lfloor \vert F\vert /k\rfloor$ for any vertex v of F.

To determine when a forest F is equitably 2-colorable needs a bit more work than that of a tree. Without loss of generality, suppose that F has r components such that each component tree T _i consists of two parts X _i and Y _i . The objective is to look for a partition of {1, 2, …, r} into two parts A and B such that $\sum _{i\in A}\vert X_{i}\vert +\sum _{j\in B}\vert Y _{j}\vert = \lfloor \vert F\vert /2\rfloor$.

Hansen et al. [66] introduced the notion of an m-bounded coloring of a graph G, i.e., a proper coloring of G such that each color class is of size at most m. The m-bounded chromatic number of G, denoted by χ _m (G), is the smallest number of colors required for an m-bounded coloring of G. This notion of colorability is closely related to equitable colorability via the following observation:

Observation.

The graph G has an m-bounded coloring using k colors if and only if the graph G′ obtained from G by adding mk − | G | isolated vertices is equitably k-colorable.

The problem of determining the m-bounded chromatic number of a tree was left open in [66]. By modifying the techniques used in [26], Chen and Lih [25] were able to determine the m-bounded chromatic number of a tree.

Theorem 14

Let T = T(X,Y ) be a nontrivial tree and let u be a vertex of maximum degree. Then one of the following holds:

• 1. χ _m(T) = 2 when $m \geq \max \{\vert X\vert,\vert Y \vert \}$.

• 2. $\chi _{m}(T) =\max \{ 3,\lceil \vert T\vert /m\rceil,\lceil (\vert T\vert -\alpha _{u}(T))/m\rceil + 1\}$ when $m <\max \{ \vert X\vert,\vert Y \vert \}$.

For a nontrivial tree T = T(X, Y ), suppose that | X | = q ₁ m + r ₁ and | Y | = q ₂ m + r ₂, where 0 ≤ r ₁, r ₂ < m. One can color the part X with q ₁ + 1 colors and the part Y with q ₂ + 1 colors. Hence, $\chi _{m}(T) \leq q_{1} + q_{2} + 2 \leq \lceil \vert T\vert /m\rceil + 1$ colors. On the other hand, it is obvious that $\lceil \vert T\vert /m\rceil \leq \chi _{m}(T)$. A tree T is said to be class A if $\chi _{m}(T) = \lceil \vert T\vert /m\rceil$ and class B if $\chi _{m}(T) = \lceil \vert T\vert /m\rceil + 1$. Jarvis and Zhou [73] gave an explicit characterization when a tree belongs to class B. Their proof can be used to determine χ _m (T) in O( | T | ³) time and produce an optimal coloring even if m is part of the input. To make a comparison, it is known [14] that the problem of determining whether a bipartite graph can be m-bounded colored with three colors is NP-complete when m is part of the input. Bentz and Picouleau [10] studied a variation of m-bounded coloring of trees.

4 The Equitable Δ-ColoringConjecture

Unlike the ordinary colorability of a graph, the equitable colorability does not satisfy monotonicity, namely, a graph can be equitably k-colorable without being equitably (k + 1)-colorable. Therefore, the ECC does not fully reveal the true nature of the equitable colorability. It seems that the maximum degree plays a crucial role here. For instance, by Theorems 5 and 6 the following conjecture proposed by Chen et al. [28] holds for bipartite graphs. This conjecture is called the equitable Δ-coloring conjecture (EΔCC).

Conjecture 4

Let G be a connected graph. If G is not a complete graph K _n , or an odd cycle C _{2n + 1}, or a complete bipartite graph K _{2n + 1, 2n + 1}, then G is equitably Δ(G)-colorable.

The conclusion of the EΔCC can be equivalently stated as $\chi _{_{=}}^{{\ast}}(G) \leq \Delta (G)$. It is also immediate to see that the EΔCC implies the ECC. In Chen, Lih, and Wu [28], EΔCC was settled for graphs whose maximum degree is at least one-half of the order. The following two lemmas supplied the basic tools for the solution. Let G ^c denote the complement graph of G. Let δ(G) and α′(G) denote the minimum degree and the edge-independence number of G, respectively.

Lemma 3

Let G be a disconnected graph. If G is different from $K_{n}^{c}$ and $K_{2n+1,2n+1}^{c}$ for all n ≥ 1, then $\alpha ^{\prime}(G)>\delta (G)$.

Lemma 4

Let G be a connected graph such that |G| > 2δ(G) + 1. Suppose the vertex set of G cannot be partitioned into a set H of size δ(G) and an independent set I of size |G| − δ(G) such that each vertex of I is adjacent to all vertices of H. Then $\alpha ^{\prime}(G)>\delta (G)$.

Theorem 15

Let G be a connected graph with $\Delta (G) \geq \vert G\vert /2$. If G is different from K _n and K _2n+1,2n+1 for all n ≥ 1, then G is equitably Δ(G)-colorable.

As pointed out by Yap, a close examination of the proof of Theorem 15 in [28] reveals that a stronger result was obtained, namely, $\chi _{_{ =}}^{{\ast}}(G) \leq \vert G\vert -\alpha ^{\prime}({G}^{c}) \leq \Delta (G)$. In a similar vein, Yap and Zhang [155] made an analysis of the complement graph and succeeded in verifying the ECC for connected graphs G such that $\vert G\vert /3 + 1 \leq \Delta (G) < \vert G\vert /2$. By combining Theorem 15, their proof can be modified to establish the following stronger result:

Theorem 16

The EΔCC holds for all connected graphs G such that Δ(G) ≥ (|G| + 1)∕3.

Along a different direction, one may try to tackle the EΔCC for special classes of graphs. By attaching appropriately chosen auxiliary graphs to a nonregular graph, attention may be restricted to regular graphs due to the following lemma [28]:

Lemma 5

The EΔCC holds if it does so for all regular graphs.

If the chromatic number of a connected cubic graph G is 2, then the EΔCC has already been established. It only needs to handle cubic graphs having chromatic number 3 to obtain the following [28]:

Theorem 17

The EΔCC holds for all connected graphs G such that Δ(G) ≤ 3.

In [85], Kierstead and Kostochka extended the above to Δ(G) ≤ 4.

5 Split Graphs

There are interesting results dealing with special families of graphs that provide positive evidence for the EΔCC. A connected graph G is called a split graph if its vertex set can be partitioned into two nonempty subsets U = { u ₁, u ₂, …, u _n } and V = { v ₁, v ₂, …, v _r } such that U induces a complete graph and V induces an independent set. Denote the split graph G as G[U; V ], and always assume that no vertex in V is adjacent to all vertices in U. A family of bipartite graphs BG(k), k ≥ 1, can be assigned to the given split graph G[U; V ] in the following way. The vertex set of BG(k) is $\{u_{ij}\mid 1 \leq i \leq n$ and $1 \leq j \leq k\} \cup V$, and {u _ij , v _t } is defined to be an edge of BG(k) if and only if u _i and v _t are nonadjacent in G. Note that BG(k) is a subgraph of BG(k + 1). The coloring of a split graph G[U; V ] is closely related to independent edges of the graphs BG(k). For instance, any given set of independent edges in BG(k) induces a partial coloring of G in the following standard way. The i-th color is used to color u _i and all those vertices in V that are matched by the edges to some u _ij , 1 ≤ j ≤ k. Chen, Ko, and Lih [29] proved the following:

Theorem 18

Let G[U;V ] be a split graph such that |U| = n and |V | = r. Let $m =\max \{ k\mid \alpha ^{\prime}(BG(k)) = kn\}$ if the set in question is nonempty; otherwise let m be zero. Then $\chi _{_{=}}^{{\ast}}(G[U;V ]) = n + \lceil (r -\alpha ^{\prime}(BG(m + 1)))/(m + 2)\rceil$.

Once $\chi _{_{=}}^{{\ast}}(G[U;V ])$ is known, it is straightforward to verify that split graphs satisfy the EΔCC.

In [29], the m-bounded chromatic number of a split graph was obtained in addition to its equitable chromatic number.

Theorem 19

Let G = G[U;V ] be a split graph such that |U| = n and |V | = r. Let m ≥ 1 be a given integer. Then $\chi _{m}(G[U;V ]) = n + \lceil (r -\alpha ^{\prime}(BG(m - 1)))/m\rceil$.

6 Outerplanar Graphs

A graph is planar if it can be drawn on the Euclidean plane such that edges only meet each other at points representing the vertices of the graph. An outerplanar graph is a planar graph that has a drawing on the plane such that every vertex lies on the unbounded face. An edge subdivision is the operation of replacing an edge uv by a path uwv of length 2 in which w is a newly added vertex. A subdivision of a graph G is a graph obtained from G by a sequence of edge subdivisions. It is well known [18] that a graph is an outerplanar graph if and only if it has no subgraph that is a subdivision of K ₄ or K _{2, 3}. Yap and Zhang [156] settled the EΔCC for outerplanar graphs.

Theorem 20

If G is an outerplanar graph with $\Delta (G) \geq 3$, then G is equitably Δ(G)-colorable.

Kostochka [91] proved the following result which answers a question posed at the end of [156]:

Theorem 21

If G is an outerplanar graph with Δ(G) ≥ 3, then $\chi _{_{=}}^{{\ast}}(G) \leq \Delta (G)/2 + 1$.

Note that the bound cannot be weakened even for trees because the star K _{1, 2k − 1} has no equitable k-coloring. An efficient algorithm for equitable k-coloring of outerplanar graphs G with maximum degree at least 3 can be extracted from Kostochka’s proof whenever k ≥ Δ(G) ∕ 2 + 1.

A fundamental phenomenon in equitable colorings can be noticed when one examines the equitable chromatic numbers of trees. Apart from K _{1, n} , “most” trees admit equitable colorings with few colors. This phenomenon happens for outerplanar graphs, too. Pemmaraju [125] showed the following:

Theorem 22

An outerplanar graph G is equitably 6-colorable if Δ(G) ≤|G|∕6.

The main stepping stone to Pemmaraju’s result involves a special partition of a graph. A partition V (G) = V ₁ ∪V ₂ is called an equitable 2-forest partition if $\vert \vert V _{1}\vert -\vert V _{2}\vert \vert \leq 1$ and each induced subgraph $G[V _{i}]$ is a forest. The following theorem and conjecture in [125] may have independent interest:

Theorem 23

Any outerplanar graph has an equitable 2-forest partition.

Conjecture 5

The vertex set of any planar graph can be partitioned into two parts V ₁ and V ₂ such that | | V ₁ | − | V ₂ | | ≤ 1 and each part induces an outerplanar subgraph.

Note that Chartrand et al. [23] have proved that the vertex set of a planar graph can be partitioned into two parts such that each part induces an outerplanar subgraph. They also conjectured that the edge set of a planar graph can be partitioned into two sets such that the subgraph induced by each of the sets is outerplanar. Recently, Gonçalves [60] has proved the validity of this conjecture.

A graph is called series-parallel if it contains no subgraph that is a subdivision of K ₄. This class of graphs can be characterized in a number of equivalent ways [18]. Clearly, outerplanar graphs are series-parallel graphs. Zhang and Wu [159] established the EΔCC for series-parallel graphs.

Theorem 24

If G is a series-parallel graph with Δ(G) ≥ 3, then G is equitably Δ(G)-colorable.

Zhang and Wu also conjectured the following which generalizes Theorem 21:

Conjecture 6

If G is a series-parallel graph with Δ(G) ≥ 3, then $\chi _{_{=}}^{{\ast}}(G) \leq \Delta (G)/2 + 1$.

7 Planar Graphs

To determine whether a planar graph with maximum degree 4 is 3-colorable is NP-complete [58]. For a given planar graph G with maximum degree 4, let G′ be obtained from G by adding 2 | G | isolated vertices. Then G is 3-colorable if and only if G′ is equitably 3-colorable. Therefore, it is NP-complete to determine if a given planar graph with maximum vertex degree 4 has an equitable coloring using at most 3 colors.

Zhang and Yap [160] proved the following:

Theorem 25

A planar graph G is equitably Δ(G)-colorable if Δ(G) ≥ 13.

Nakprasit [117] extended the above result to planar graphs with maximum degree at least 9. Thus, the EΔCC holds for planar graphs with maximum degree at least 9. One can go further if extra conditions are imposed on the graph.

Theorem 26 ([118, 137])

Let G be a C ₄ -free planar graph. If Δ(G) ≥ 7, then the EΔCC holds for G.

Zhu and Bu [162] established the following results. Consequently, the EΔCC holds for planar graphs G that are (i) C ₃-free and Δ(G) ≥ 8 or (ii) C ₄-free, C ₅-free, and Δ(G) ≥ 7.

Theorem 27

Let G be a C ₃ -free planar graph. Then $\chi _{_{=}}^{{\ast}}(G) \leq \max \{ \Delta (G),8\}$.

Theorem 28

Let G be a C ₄ -free and C ₅ -free planar graph. Then $\chi _{_{=}}^{{\ast}}(G) \leq \max \{ \Delta (G),7\}$.

The girth of a graph G, denoted by g(G), is defined to be the length of a shortest cycle in G. The girth of a forest is ∞ by convention. One may impose conditions on the girth of a planar graph to get tight bound for the equitable chromatic threshold. Wu and Wang [153] first established the following:

Theorem 29

Let G be a planar graph with δ(G) ≥ 2.

• 1. If g(G) ≥ 14, then $\chi _{_{=}}^{{\ast}}(G) \leq 4$.

• 2. If g(G) ≥ 26, then $\chi _{_{=}}^{{\ast}}(G) \leq 3$.

Luo et al. [108] improved these results further.

Theorem 30

Let G be a planar graph with δ(G) ≥ 2.

• 1. If g(G) ≥ 10, then $\chi _{_{=}}^{{\ast}}(G) \leq 4$.

• 2. If g(G) ≥ 14, then $\chi _{_{=}}^{{\ast}}(G) \leq 3$.

It remains an open problem to find the best possible girth conditions for 3- or 4-equitable colorability when the planar graph G satisfies δ(G) ≥ 2.

A well-known theorem of Grötzsch [61] states that the chromatic number of any planar graph of girth at least 4 is at most 3. Hence, the above theorem has an immediate consequence.

Corollary 1

Let G be a non-bipartite planar graph with δ(G) ≥ 2. Then $\chi (G) =\chi _{ _{=}}^{{\ast}}(G)$ if g(G) ≥ 14.

8 Graphs with Low Degeneracy

A graph with small degeneracy can be regarded as “sparse.” A graph G is said to be d-degenerate if every subgraph H of G has a vertex of degree at most d in H. It is well known that graphs without edges are 0-degenerate, forests are exactly the 1-degenerate graphs, outerplanar graphs are 2-degenerate, and planar graphs are 5-degenerate. It follows from the definition that the vertices of every d-degenerate graph can be ordered as v ₁, v ₂, …, v _n so that for every i < n, vertex v _i has at most d neighbors v _j with j > i.

The following results were obtained by Zhu and Bu [163]:

Theorem 31

Let G be a 2-degenerate graph. Then G is equitably 3-colorable if $\|G\| \leq \frac{2} {3}\vert G\vert$.

Theorem 32

Let G be a 2-degenerate graph. Then G is equitably 4-colorable if $\|G\| \leq \frac{3} {4}\vert G\vert$.

Kostochka and Nakprasit [92] tried to find bounds on the equitable chromatic thresholds for d-degenerate graphs with a given maximum degree. However, the bound in Theorem 21 on outerplanar graphs does not extend to all 2-degenerate graphs. To see this, consider the graph $G(d,\Delta ) = K_{d} \vee I_{\Delta -d+1}$, where the join operation $\vee$ connects each vertex in one graph to all vertices of the other graph. This graph is d-degenerate and of maximum degree Δ. In every proper coloring of G(d, Δ), each vertex in K _d forms a single color class. Hence, every equitable coloring of G(d, Δ) uses at least $d + \lceil (\Delta - d + 1)/2\rceil = \lceil (\Delta + d + 1)/2\rceil$ colors. In particular, G(2, Δ) uses at least ⌈(Δ + 3) ∕ 2⌉ colors for an equitable coloring, which is greater than ⌈Δ ∕ 2⌉ + 1 for even Δ. Kostochka and Nakprasit showed that ⌈(Δ + d + 1) ∕ 2⌉ colors is enough to equitably color a d-degenerate graph G with maximum degree Δ provided Δ ∕ d is large.

Theorem 33

Let $2 \leq d \leq \Delta /27$ and G be a d-degenerate graph with maximum degree at most Δ. Then G is equitably k-colorable if k ≥ (Δ + d + 1)∕2.

The example G(d, Δ) shows that the bound on k cannot be decreased. The next corollary follows from this theorem since every planar graph is 5-degenerate.

Corollary 2

Let $\Delta \geq 135$ and the maximum degree of the planar graph G be at most Δ. Then G is equitably k-colorable if k ≥ Δ∕2 + 3.

Let k ≥ 14d + 1 and the d-degenerate graph G have maximum degree at most k. Then, for Δ = 2k − 1 − d, G satisfies the condition of Theorem 33.

Corollary 3

Let d ≥ 2. Then every d-degenerate graph with maximum degree at most k is equitably k-colorable if k ≥ 14d +1.

In view of Theorem 33, which is also true if d = Δ by the Hajnal and Szemerédi Theorem, the following was proposed in [92]:

Conjecture 7

Let 2 ≤ d ≤ Δ and G be a d-degenerate graph with maximum degree at most Δ. Then G is equitably k-colorable if k ≥ (Δ + d + 1) ∕ 2.

A graph with “low degeneracy” is intuitively rather similar to a graph whose every subgraph has a “small average degree.” Kostochka and Nakprasit [93] proved the EΔCC for graphs that have “small average degree” without restrictions on their subgraphs. The average degree of a graph G is defined to be Ad(G) = 2 ∥ G ∥ ∕ | G |.

Theorem 34

Let Δ ≥ 46 and G be a graph of order at least 46 and maximum degree at most Δ. If Ad(G) ≤ Δ∕5 and $K_{\Delta +1}$ is not a subgraph of G, then G is equitably Δ-colorable.

An immediate consequence of this result is that the EΔCC holds for d-degenerate graphs with maximum degree Δ if d ≤ Δ ∕ 10.

In Kostochka et al. [95], a result similar to Theorem 22 was established for d-degenerate graphs.

Theorem 35

Every d-degenerate graph G with maximum degree at most Δ is equitably k-colorable when k ≥ 16d and Δ ≤|G|∕15.

If the restriction on Δ is removed, they proved the following:

Theorem 36

Every d-degenerate graph G with maximum degree at most Δ is equitably k-colorable for any k, $k \geq \max \{ 62d,31d\vert G\vert /(\vert G\vert - \Delta + 1)\}$.

Corollary 4

Every d-degenerate graph G with maximum degree at most |G|∕2 + 1 is equitably k-colorable for any k ≥ 62d.

The proof of Theorem 36 is constructive, and by extending their proof method, the following result of algorithmic nature was obtained:

Theorem 37

There exists a polynomial time algorithm that produces an equitable k-coloring of G for every equitably m-colorable d-degenerate graph G if k ≥ 31dm.

A concept generalizing Pemmaraju’s “equitable 2-forest partition” was also introduced in [95]. An equitable k-partition of a graph G is a collection of subgraphs {G[V ₁], G[V ₂], …, G[V _k ]} of G induced by the vertex partition {V ₁, V ₂, …, V _k } of V (G) such that | | V _i | − | V _j | | ≤ 1 for every pair V _i and V _j . The following provides a tool for obtaining equitable colorings with few colors:

Theorem 38

Let k ≥ 3 and d ≥ 2. Then every d-degenerate graph has an equitable k-partition into (d − 1)-degenerate graphs.

This is an extension of Theorem 1 proved by Bollobás and Guy, which can be restated as follows: Any 1-degenerate graph G with Δ(G) ≤ | G | ∕ 3 can be equitably 3-partitioned into 0-degenerate graphs. Pemmaraju et al. [126] gave a direct generalization.

Theorem 39

For d ≥ 1, every d-degenerate graph G with Δ(G) ≤|G|∕3 can be equitably 3-partitioned into (d − 1)-degenerate graphs.

Repeated applications of this theorem can get the following:

Theorem 40

For d ≥ 1, every d-degenerate graph G with Δ(G) ≤|G|∕3^d can be equitably 3 ^d -colored.

In the same paper, the following conjecture was proposed:

Conjecture 8

There are functions f(d) = O(d) and g(d) = O(d) such that if G is a d-degenerate graph with Δ(G) ≤ | G | ∕ f(d), then G can be equitably g(d)-colored.

9 Graphs of Bounded Treewidth

A tree decomposition of a graph G is a pair ($(T,\mathcal{F})$), with T a tree and $\mathcal{F} =\{ X_{i} \subseteq V (G)\mid i \in V (T)\}$, that satisfies the following conditions:

• 1. $\bigcup _{i\in V (T)}X_{i} = V (G)$.

• 2. For every edge uv of G, there exists an i ∈ V (T) such that X _i contains both u and v.

• 3. For all i ₁, i ₂, i ₃ ∈ V (T), $X_{i_{1}} \cap X_{i_{3}} \subseteq X_{i_{2}}$ if i ₂ is on the path from i ₁ to i ₃ in T.

The width of the tree decomposition $(T,\mathcal{F})$ is defined to be $\max _{i\in V (T)}\vert X_{i}\vert - 1$; the treewidth of a graph G denoted by tw(G) is the minimum width among all tree decompositions of G. It is a folklore result that every graph G of treewidth at most k has a vertex of degree at most k and has at most k | G | edges. Hence, every graph of treewidth at most k is k-degenerate.

The class of graphs with treewidth at most k can be characterized in terms of partial k-trees. The class of k-trees is defined recursively as follows:

• 1. The complete graph K _k is a k-tree.

• 2. A k-tree G with n + 1 vertices (n ≥ k) is constructed from a k-tree H with n vertices by adding a new vertex adjacent to and only to all vertices of a subgraph of H that is a K _k .

There are a number of alternative characterizations of k-trees [129]. A graph is called a partial k-tree if it is a subgraph of a k-tree. Forests are partial 1-trees and series-parallel graphs are partial 2-trees.

Theorem 41 ([139])

A graph G is a partial k-tree if and only if G has treewidth at most k.

A corollary of Theorem 36 is the following:

Corollary 5

Every graph G with treewidth w and maximum degree at most Δ is equitably k-colorable for any k, $k \geq \max \{ 62w,31w\vert G\vert /(\vert G\vert - \Delta + 1)\}$.

The equitable k-coloring problem can be stated as follows. A graph G and an integer k are given, and one asks whether G has an equitable k-coloring. For graphs of bounded treewidth, Bodlaender and Fomin [13] used the above result to establish the threshold for telling when the EQUITABLE k-COLORING problem is trivially solved and when it becomes to be solvable in polynomial time by their dynamic programming approach. It amounts to the following.

Theorem 42

The equitable k-coloring problem can be solved in polynomial time on graphs of bounded treewidth.

They also showed that such an approach cannot be extended to the equitable k-coloring with precoloring problem: A graph G, an integer k, and a precoloring π of G are given, and one asks whether there exists an equitable k-coloring of G extending π. For a graph G, a precoloringπ of a subset U of vertices of G in k colors is a mapping $\pi : U \rightarrow \{ 1,2,\ldots,k\}$. A coloring of G with color classes V ₁, V ₂, …, V _k is said to extend the precoloring π if $u \in V _{\pi (u)}$ for every u ∈ U. The following was proved in [13]:

Theorem 43

The equitable k-coloring with precoloring problem is NP-complete on trees.

In the framework of parameterized complexity, e.g., [41, 51], and [119], a parameterized problem with the input size n and a parameter k is called fixed parameter tractable (FPT) if it can be solved in time $f(k) \cdot {n}^{c}$, where f is a function only depending on k and c is a constant. The basic complexity class for fixed parameter intractability is $\mathcal{W}[1]$. The equitable coloring problem was shown by Fellow et al. [47] to be $\mathcal{W}[1]$-hard, parameterized by the treewidth plus the number of colors. However, the equitable coloring problem is FPT when parameterized by the vertex cover number as shown by Fiala et al. [48]. The vertex cover number of a graph G is the minimum size of a set $X \subseteq V (G)$ such that $V (G) \setminus X$ is an independent set.

10 Kneser Graphs

For integers $i \leq j$, let $[i,j] =\{ i,i + 1,\ldots,j\}$ and [n] = [1, n]. If X is a set, then the collection of all k-subsets of X is denoted by $\left ({ X \atop k} \right )$. The Kneser graph $\mathsf{KG}(n,k)$ has $\left ({ [n] \atop k} \right )$ as its vertex set. Two distinct vertices are adjacent in $\mathsf{KG}(n,k)$ if they have empty intersection as subsets. To exclude trivialities, it is always assumed that n > 2k in $\mathsf{KG}(n,k)$. The order of $\mathsf{KG}(n,k)$ is clearly $\left ({ n \atop k} \right )$. The odd graphO _k is the Kneser graph $\mathsf{KG}(2k + 1,k)$. Since it is easy to see that $\mathsf{KG}(n,1) = K_{n}$ and $\chi (\mathsf{KG}(n,1)) =\chi _{_{=}}(\mathsf{KG}(n,1)) =\chi _{ _{=}}^{{\ast}}(\mathsf{KG}(n,1)) = n$, it is assumed that k ≥ 2 throughout this section.

The following is a much celebrated result of Lovász [107] proved by topological method:

Theorem 44

The chromatic number of $\mathsf{KG}(n,k)$ is equal to n − 2k + 2.

For i ∈ [n], an i-flower $\mathcal{F}$ of $\left ({ [n] \atop k} \right )$ is a subcollection of $\left ({ [n] \atop k} \right )$ such that all k-subsets in $\mathcal{F}$ have i as a common element. It is clear that every i-flower is an independent set of $\mathsf{KG}(n,k)$. Any independent set $\mathcal{F}$ of $\mathsf{KG}(n,k)$, also called an intersecting family of $\left ({ [n] \atop k} \right )$, satisfies $A \cap B\neq \varnothing$ for all A and B in $\mathcal{F}$. The independence number $\alpha (\mathsf{KG}(n,k))$ of $\mathsf{KG}(n,k)$ was obtained by Erdős et al. [44].

Theorem 45

Suppose $\mathcal{F}$ is an intersecting family of $\left ({ [n] \atop k} \right )$. Then

$$\vert \mathcal{F}\vert \leq \left ({ n - 1 \atop k - 1} \right ).$$

Moreover, the equality holds if and only if $\mathcal{F}$ is an i-flower for some i ∈ [n]. Hence, $\alpha (\mathsf{KG}(n,k)) = \left ({ n-1 \atop k-1} \right )$.

There are independent sets of $\mathsf{KG}(n,k)$ which are not flowers. Denote by $\alpha _{2}(\mathsf{KG}(n,k))$, or simply $\alpha _{2}(n,k)$, the maximum size of independent sets $\mathcal{H}$ of $\mathsf{KG}(n,k)$ satisfying $\bigcap _{A\in \mathcal{H}}A$ = ∅ and α ₂(n, k) was obtained by Hilton and Milner [69].

Theorem 46

Suppose $\mathcal{H}$ is an intersecting family of $\left ({ [n] \atop k} \right )$ with $\bigcap _{A\in \mathcal{H}}A = \varnothing$. Then

$$\vert \mathcal{H}\vert \leq \left ({ n - 1 \atop k - 1} \right ) -\left ({ n - k - 1 \atop k - 1} \right ) + 1.$$

Moreover, the equality holds if $\mathcal{H}$ is the family $\{A \in \left ({ [n] \atop 3} \right )\mid \vert A \cap [1,3]\vert \geq 2\}$ when k=3 or $\mathcal{H}$ is the family $\{A \in \left ({ [n] \atop k} \right )\mid 1 \in A,\vert A \cap [2,k + 1]\vert \geq 1\} \cup \{ [2,k + 1]\}$. Hence, $\alpha _{2}(n,k) = \left ({ n-1 \atop k-1} \right ) -\left ({ n-k-1 \atop k-1} \right ) + 1$.

Since every flower of $\left ({ [n] \atop k} \right )$ is an independent set of $\mathsf{KG}(n,k)$, it is natural to partition flowers to form an equitable coloring of $\mathsf{KG}(n,k)$. If this is successful, then every k-subset of [n] is in some flower. Hence, if f is an equitable m-coloring of $\mathsf{KG}(n,k)$ such that every color class of f is contained in some flower, then m ≥ n − k + 1. Otherwise, suppose m ≤ n − k and each color class f ^{− 1}(i) is contained in some t _i -flower for 1 ≤ i ≤ m. Since $\vert [n] \setminus \{ t_{1},t_{2},\ldots,t_{m}\}\vert \geq n - m \geq k$, one may choose a k-subset $A \subseteq [n] \setminus \{ t_{1},t_{2},\ldots,t_{m}\}$. Since f is an equitable m-coloring, $A \in {f}^{-1}(i)$ for some i, i.e., t _i ∈ A. Thus, a contradiction is obtained.

In [24], Chen and Huang tried to show that $\mathsf{KG}(n,k)$ is equitably m-colorable for all m ≥ n − k + 1 by partitioning flowers of $\left ({ [n] \atop k} \right )$ into m-independent sets whose sizes are as even as possible. They succeeded in establishing the following:

Theorem 47

Suppose that $m \geq n - k + 1$. Then $\mathsf{KG}(n,k)$ is equitably m-colorable, i.e., $\chi _{_{=}}(\mathsf{KG}(n,k)) \leq \chi _{_{=}}^{{\ast}}(\mathsf{KG}(n,k)) \leq n - k + 1$.

Lemma 6

Suppose that m ≤ n − k and $\left \lfloor \left ({ n \atop k} \right )/m\right \rfloor>\alpha _{2}(n,k)$. Then $\mathsf{KG}(n,k)$ is not equitably r-colorable for all $r \leq m$, i.e., $\chi _{_{=}}^{{\ast}}(\mathsf{KG}(n,k)) \geq \chi _{_{=}}(\mathsf{KG}(n,k)) \geq m + 1$.

Theorem 48

If $\left \lfloor \left ({ n \atop k} \right )/(n - k)\right \rfloor>\alpha _{2}(n,k)$, then $\chi _{_{=}}(\mathsf{KG}(n,k)) =\chi _{ _{=}}^{{\ast}}(\mathsf{KG}(n,k)) = n - k + 1$.

Observe that $\left ({ n \atop k} \right )/(n - k) = O({n}^{k-1})$ and $\alpha _{2}(n,k) = O({n}^{k-2})$. Hence, the following is true.

Corollary 6

Let k be fixed. Then $\chi _{_{ =}}(\mathsf{KG}(n,k)) =\chi _{ _{=}}^{{\ast}}(\mathsf{KG}(n,k)) = n - k + 1$ when n is sufficiently large.

Finally, $\chi _{_{=}}(\mathsf{KG}(n,2))$, $\chi _{_{ =}}(\mathsf{KG}(n,3))$, and χ(O _k ) were completely determined in [24].

Theorem 49

Assume n ≥ 5. Then

$$\chi _{_{=}}(\mathsf{KG}(n,2)) =\chi _{ _{=}}^{{\ast}}(\mathsf{KG}(n,2)) = \left \{\begin{array}{ll} n - 2&\mbox{ if}\quad n = 5\,or\,6, \\ n - 1&\mbox{ if}\quad n \geq 7. \end{array} \right.$$

Theorem 50

Assume n ≥ 7. Then

$$\chi _{_{=}}(\mathsf{KG}(n,3)) =\chi _{ _{=}}^{{\ast}}(\mathsf{KG}(n,3)) = \left \{\begin{array}{ll} n - 4&\quad \mbox{ if}\quad 7 \leq n \leq 13,\\ n - 3 &\quad \mbox{ if} \quad 14 \leq n \leq 15, \\ n - 2&\quad \mbox{ if}\quad n \geq 16. \end{array} \right.$$

Theorem 51

For k ≥ 1, the odd graph O _k satisfies $\chi (O_{k}) =\chi _{_{=}}(O_{k}) =\chi _{ _{=}}^{{\ast}}(O_{k}) = 3$.

Chen and Huang concluded their paper [24] by proposing the following:

Conjecture 9

If n > 2k ≥ 4, then $\chi _{_{=}}(\mathsf{KG}(n,k)) =\chi _{ _{=}}^{{\ast}}(\mathsf{KG}(n,k))$.

All results about Kneser graphs in this section were also independently obtained by Fidytek et al. [49].

11 Interval Graphs and Others

A graph G is called an interval graph if there exists a family $\mathcal{I} =\{ I_{v}\mid v \in V (G)\}$ of intervals on the real line such that u and v are adjacent vertices if and only if $I_{u} \cap I_{v}\neq \varnothing$. Such a family $\mathcal{I}$ is commonly referred to as an interval representation of G. Instead of intervals of real numbers, these intervals may be replaced by finite intervals on a linearly ordered set.

A clique of a graph G is a complete subgraph Q of G. A clique is called maximal if it is maximal in the set-inclusion order. For an interval graph G, Gillmore and Hoffman [59] showed that its maximal cliques can be linearly ordered as Q ₀ < Q ₁ < ⋯ < Q _m so that for every vertex v of G, the maximal cliques containing v occur consecutively. The finite interval I _v = [Q _i , Q _j ] in this linear order is assigned to the vertex v if all the maximal cliques containing v are precisely $Q_{i},Q_{i+1},\ldots,Q_{j}$. Again u and v are adjacent if and only if $I_{u} \cap I_{v}\neq \varnothing$. This representation of G is called a clique path representation of G. Conversely, the existence of a clique path representation implies that the graph is an interval graph.

Once a clique path representation is given, let left(v) and right(v) stand for the left and right endpoint, respectively, of the interval I _v . Then the following linear order on the vertices of G can be defined. Let u < v if (left(u) < left(v)) or (left(u) = left(v) and right(u) < right(v)). If u and v have the same left and right endpoints, choose u < v arbitrarily. For any three vertices u, v, and w of G, this linear order satisfies the following condition. If u < v < w and uw ∈ E(G), then uv ∈ E(G). The existence of a linear order satisfying this condition characterizes interval graphs [120]. Chen et al. [31] utilized this linear order to obtain the following:

Theorem 52

Let G be a connected interval graph. If G is not a complete graph, then G is equitably Δ(G)-colorable.

And they proceeded further to show the following:

Theorem 53

Let G be an interval graph. Then $\chi _{_{=}}(G) =\chi _{ _{=}}^{{\ast}}(G)$.

A few other classes of special graphs have been investigated for their equitable colorability. For instance, central graphs and total graphs were studied in [2, 140]. Thorny graphs were studied in [56]. Additional examples can be found in [57, 76–78].

For a given graph G, the so-called central graphC(G) of G is obtained from G by inserting a new vertex to each edge of G and then joining each pair of vertices of G which were nonadjacent in G. The total graph T(G) of G has vertex set $V (G) \cup E(G)$ and edges joining all elements of this vertex set which are adjacent or incident in G. The notation P _n represents a path on n vertices.

Results obtained in [2, 140] are listed as follows:

• 1. $\chi _{_{=}}(C(K_{1,n})) = n$.

• 2. $\chi _{_{=}}(C(K_{n,n})) \geq n$ if n ≥ 3.

• 3. $\chi _{_{=}}(C(K_{n})) = 3$.

• 4. $\chi _{_{=}}(C(P_{n})) = \left \{\begin{array}{ll} 1 &\mbox{ if }\ \ n = 1, \\ 2 &\mbox{ if }\ \ n = 2, \\ 3 &\mbox{ if }\ \ n = 3, \\ 3 &\mbox{ if }\ \ n = 4, \\ n/2 &\mbox{ if }\ \ n \geq 5\,\text{is\,even}, \\ (n + 1)/2&\mbox{ if }\ \ n \geq 5\,\text{is\,odd}.\end{array} \right.$

• 5. $\chi _{_{=}}(C(C_{n})) = \left \{\begin{array}{ll} 2 &\mbox{ if }\ \ n = 3, \\ 3 &\mbox{ if }\ \ n = 4, \\ n/2 &\mbox{ if }\ \ n \geq 5\,\text{is\,even}, \\ (n + 1)/2&\mbox{ if }\ \ n \geq 5\,\text{is\,odd}.\end{array} \right.$

• 6. $\chi _{_{=}}(T(K_{m,n})) = \left \{\begin{array}{ll} n + 1&\ \mbox{ if }\ \ m < n,\\ n + 2 &\ \mbox{ if } \ \ m = n,\end{array} \right.$

• 7. $\chi _{_{=}}(T(P_{n})) = 3$.

• 8. $\chi _{_{=}}(T(C_{n})) = 3\mbox{ if }\,n \,\text{is\,a\,multiple\,of}\,3.$

An edge in a graph is called an pendant edge if it is incident with a leaf, i.e., a vertex of degree 1. Trees are the smallest set of graphs that contains single vertex and is closed under the operation of attaching a pendant edge to a vertex. By analogy to this recursive definition of trees, graphs called edge-cacti, cacti, and thorny graphs can be defined as follows.

Edge-cacti constitute the smallest set of graphs that includes all cycles and is closed under the operation of attaching a cycle to a single edge, i.e., identifying this edge with some edge of the attached cycle. Cacti constitute the smallest set of graphs that contains single vertex and is closed under the operation of attaching a pendant edge or cycle to a vertex. Thorny graphs constitute the smallest set of graphs that includes single vertex and is closed under the following operations:

• 1. Attaching a pendant edge to a vertex

• 2. Attaching a cycle to a vertex

• 3. Attaching a cycle to an edge

Every thorny graph is connected, planar, and tripartite. All cacti, edge-cacti, and connected outerplanar graphs are thorny graphs. The following results were established in [56]:

Theorem 54

Any thorny graph without leaves and C ₃ or C ₅ is equitably 3-colorable.

Theorem 55

Any thorny graph without leaves and C ₃ is equitably k-colorable for all k ≥ 4.

Corollary 7

The following statements are true:

• 1. Any edge-cactus without C ₃ is equitably k-colorable for all k ≥ 3. Furthermore, if an edge-cactus G is bipartite, then $\chi _{_{=}}(G) = 2$.

• 2. Any cactus without leaves and C ₃ or C ₅ is equitably k-colorable for all k ≥ 3.

• 3. Any bipartite cactus without leaves is equitably k-colorable for all k ≥ 3.

• 4. Any cactus without leaves and C ₃ is equitably k-colorable for all k ≥ 4.

12 Random Graphs

Let G(n, p) denote the probability space of all labeled graphs of order n such that every edge appears randomly and independently with probability p = p(n). The space G(n, p) is said to possess a property $\mathcal{P}$ almost surely if the probability that G(n, p) satisfies $\mathcal{P}$ tends to 1 as n tends to infinity. In [98], Krivelevich and Patkós conjectured the following:

Conjecture 10

There exists a constant C such that if C ∕ n < p < 0. 99, then almost surely $\chi _{_{=}}^{{\ast}}(G(n,p)) = (1 + o(1))\chi (G(n,p))$ holds.

Partial results proved by them included the following:

• 1. If n ^{− 1 ∕ 5 + ε} < p < 0. 99 for some positive ε, then almost surely $\chi _{_{=}}(G(n,p)) \leq (1 + o(1))\chi (G(n,p))$ holds.

• 2. There exists a constant C such that if C ∕ n < p < 0. 99, then almost surely $\chi _{_{=}}(G(n,p)) \leq (2 + o(1))\chi (G(n,p))$ holds.

• 3. If n ^{− (1 − ε)} < p < 0. 99 for some positive ε, then almost surely $\chi _{_{=}}^{{\ast}}(G(n,p)) \leq (2 + o(1))\chi (G(n,p))$ holds.

• 4. If ${(\log }^{1+\epsilon }n)/n < p < 0.99$ for some positive ε, then almost surely $\chi _{_{=}}^{{\ast}}(G(n,p)) = O_{\epsilon }(\chi (G(n,p)))$ holds.

13 Graph Products

Given two graphs G ₁ and G ₂, it is natural to use the Cartesian product V (G ₁) ×V (G ₂) of the two vertex sets to be the vertex set of a new graph. There are several ways to define the edge set of such a product graph. Results on three different products will be surveyed. Their edge sets are defined as follows:

• 1. The square product G ₁ □G ₂, also known as the Cartesian product:

  $E(G_{1}\square G_{2}) =\{ (u,x)(v,y)\mid (u = v\mbox{ and }xy \in E(G_{2}))\mbox{ or }(x = y\mbox{ and }uv \in E(G_{1}))\}$.

• 2. The cross product G ₁ ×G ₂, also known as the Kronecker, direct, tensor, weak tensor, or categorical product:

  $E(G_{1} \times G_{2}) =\{ (u,x)(v,y)\mid uv \in E(G_{1})\mbox{ and }xy \in E(G_{2})\}$.

• 3. The strong product $G_{1} \boxtimes G_{2}$, also known as the strong tensor product:

  $E(G_{1}\boxtimes G_{2}) =\{ (u,x)(v,y)\mid (u = v\mbox{ and }xy \in E(G_{2}))\mbox{ or }(uv \in E(G_{1})\mbox{ and }x = y)\mbox{ or }(uv \in E(G_{1})\mbox{ and }xy \in E(G_{2}))\}$.

Note that square and cross products are so named because the products of two single edges are a square and a cross, respectively, and $G_{1} \boxtimes G_{2} = (G_{1}\square G_{2}) \cup (G_{1} \times G_{2})$.

13.1 Square Product

For the ordinary chromatic number, Sabidussi [130] proved a product theorem.

Theorem 56

For graphs G ₁ and G ₂, $\chi (G_{1}\square G_{2}) =\max \{\chi (G_{1}),\chi (G_{2})\}$.

In Chen et al. [31], the following results were obtained:

Theorem 57

If G ₁ and G ₂ are equitably k-colorable, so is $G_{1}\square G_{2}$.

Corollary 8

For graphs G ₁ and G ₂, $\chi _{_{ =}}^{{\ast}}(G_{ 1}\square G_{2}) \leq \max \{\chi _{_{=}}^{{\ast}}(G_{ 1}),\chi _{_{=}}^{{\ast}}(G_{ 2})\}$.

Corollary 9

If $\chi (G_{1}) =\chi _{ _{=}}^{{\ast}}(G_{1})$ and $\chi (G_{2}) =\chi _{ _{=}}^{{\ast}}(G_{2})$, then $\chi (G_{1}\square G_{2}) =\chi _{_{=}}(G_{1}\square G_{2}) =\chi _{ _{=}}^{{\ast}}(G_{1}\square G_{2}) =\max \{\chi (G_{1}),\chi (G_{2})\}$.

Corollary 10

Let $G = G_{1}\square G_{2}\square \cdots \square G_{n}$, where each G _i is a path, a cycle, or a complete graph. Then $\chi (G) =\chi _{_{=}}(G) =\chi _{ _{=}}^{{\ast}}(G) =\max \{\chi (G_{i})\mid 1 \leq i \leq n\}$.

Corollary 11

Suppose that G ₁ and G ₂ are nontrivial graphs. Then G ₁ □G ₂ is equitably $\Delta (G_{1}\square G_{2})$ -colorable, i.e., the EΔCC holds for the square product of two graphs.

Even if $\chi (G_{1}) =\chi _{_{=}}(G_{2}) = k$, the product G ₁ □G ₂ may not be equitably k-colorable. An example is the product K _{1, 5} □P ₃. If it is assumed that $\chi _{_{=}}(G_{1}) =\chi _{_{=}}(G_{2}) = k$, it may not lead to the conclusion $\chi _{_{=}}(G_{1}\square G_{2}) = k$. An example is $K_{1,2n}\square K_{1,2n}$. If $G_{1} = K_{3,3}$ and $G_{2} = K_{1,1,2}$, then $\chi _{_{=}}(G_{1}\square G_{2}) \leq \max \{\chi _{_{=}}(G_{1}),\chi _{_{=}}(G_{2})\}$ is false.

Exact values for paths, cycles, and complete graphs are also determined in [31].

Theorem 58

The following hold for positive integers m and n:

$\chi (P_{m}\square P_{n}) =\chi _{_{=}}(P_{m}\square P_{n}) =\chi _{ _{=}}^{{\ast}}(P_{m}\square P_{n}) = 2$.

$\chi (C_{m}\square C_{n}) =\chi _{_{=}}(C_{m}\square C_{n}) =\chi _{ _{=}}^{{\ast}}(C_{m}\square C_{n}) = \left \{\begin{array}{ll} 2&\ if\,m\,and\,n\,are\,even,\\ 3 &\ otherwise. \end{array} \right.$

$\chi (K_{m}\square K_{n}) =\chi _{_{=}}(K_{m}\square K_{n}) =\chi _{ _{=}}^{{\ast}}(K_{m}\square K_{n}) =\max \{ m,n\}$.

Furmańczyk [54] also obtained a number of exact values of square products between cycles, paths, and hypercubes $Q_n = \underbrace {k_2\square k_2...\square k_2.}_n$.

Theorem 59

Let k,m,n, and r be positive integers. Then the following graphs have their equitable chromatic numbers all equal 2: $Q_{r}\square P_{2n}$, $Q_{r}\square C_{2n}$, and $Q_{r}\square Q_{r}$.

Besides $\chi _{_{=}}(K_{m_{1},n_{1}}\square K_{m_{2},n_{2}}) \leq 4$, Lin in his Ph.D. dissertation [103] (also in [105]) determined more exact values. They are listed as follows, in which m, n,  and r are assumed to be positive integers.

• 1. $\chi _{_{=}}(P_{2r}\square K_{m,n}) =\chi _{ _{=}}^{{\ast}}(P_{2r}\square K_{m,n}) = 2$ except $\chi _{_{=}}^{{\ast}}(P_{2}\square K_{m,n}) = 4$ when m + n + 2 < 3min{m, n}.

• 2. $\chi _{_{=}}(P_{2r+1}\square K_{m,n}) =\chi _{ _{=}}^{{\ast}}(P_{2r+1}\square K_{m,n}) = \left \{\begin{array}{ll} 2&\mbox{ if }\vert m - n\vert \leq 1,\\ 3 &\mbox{ otherwise.}\end{array} \right.$

• 3. $\chi _{_{=}}(C_{2r}\square K_{m,n}) =\chi _{ _{=}}^{{\ast}}(C_{2r}\square K_{m,n}) = 2$ except $\chi _{_{=}}^{{\ast}}(C_{4}\square K_{m,n}) = 4$ when m + n + 2 < 3min{m, n}.

• 4. $\chi _{_{=}}(C_{2r+1}\square K_{m,n}) =\chi _{ _{=}}^{{\ast}}(C_{2r+1}\square K_{m,n}) = 3$.

• 5. $\chi _{_{=}}(K_{1,m}\square K_{1,n}) =\chi _{ _{=}}^{{\ast}}(K_{1,m}\square K_{1,n}) = \left \{\begin{array}{ll} 4&\mbox{ if }(m - 2)(n - 2)> 5,\\ 3 &\mbox{ otherwise.}\end{array} \right.$

Lin also proposed some interesting conjectures:

Conjecture 11

If G ₁ and G ₂ are bipartite graphs, then $\chi _{_{=}}^{{\ast}}(G_{1}\square G_{2}) \leq 4$.

Conjecture 12

If G ₁ and G ₂ are connected graphs, then $\chi _{_{=}}(G_{1}\square G_{2}) \leq \chi (G_{1})\chi (G_{2})$.

The connectedness is essential in the above conjecture because $\chi _{_{ =}}(K_{1,3}\square 3K_{1}) =\chi _{ _{=}}^{{\ast}}(K_{ 1,3}\square 3K_{1}) = 3> 2 =\chi (K_{1,3})\chi (3K_{1})$.

13.2 Cross Product

The most well-known conjecture for cross product is the one proposed by Hedetniemi [67].

Conjecture 13

For graphs G ₁ and G ₂, χ(G ₁ ×G ₂) = min{ | G ₁ |, | G ₂ | }.

This has been established for complete graphs in [42]. For two recent surveys on Hedetniemi’s conjecture, the reader is referred to Sauer [131] and Zhu [161]. Furmańczyk [54] showed that $\chi _{_{ =}}(P_{3} \times P_{3}) = 3> 2 =\chi _{_{=}}(P_{3})$. Thus, $\chi _{_{=}}(G_{1} \times G_{2}) \leq \min \{\chi _{_{=}}(G_{1}),\chi _{_{=}}(G_{2})\}$ does not hold in general. However, Chen et al. [31] gave the following upper bound.

Theorem 60

For graphs G ₁ and G ₂, $\chi _{_{ =}}(G_{1} \times G_{2}) \leq \min \{\vert G_{1}\vert,\vert G_{2}\vert \}$.

The upper bound is sharp in the case $\chi _{_{ =}}(K_{m}\times K_{n}) =\min \{ m,n\}$. In general, min{ | G ₁ |, | G ₂ | } is not an upper bound for $\chi _{_{ =}}^{{\ast}}(G_{ 1} \times G_{2})$. An example was given in [31] to show that K ₂ ×K _n is not equitably (n + 1) ∕ 2-colorable when n > 1 and $n\chi _{_{=}}\equiv 1 ({\rm mod} 4)$. Even $\chi _{_{ =}}^{{\ast}}(G_{ 1} \times G_{2}) \leq \max \{\chi _{_{=}}^{{\ast}}(G_{ 1}),\chi _{_{=}}^{{\ast}}(G_{ 2})\}$ fails in general. Examples are $\chi _{_{=}}^{{\ast}}(K_{2,3} \times K_{2,3}) = 3> 2 =\chi _{ _{=}}^{{\ast}}(K_{2,3})$ [31] and $\chi _{_{=}}^{{\ast}}(P_{3} \times P_{3}) = 3> 2 =\chi _{ _{=}}^{{\ast}}(P_{3})$ [54]. The following result was conjectured in [31] and later proved to be true in [103]:

Theorem 61

For graphs G ₁ and G ₂, $\chi _{_{ =}}^{{\ast}}(G_{ 1} \times G_{2}) \leq \max \{\vert G_{1}\vert,\vert G_{2}\vert \}$.

It suffices to prove the above theorem for the case K _m ×K _n . A slightly better upper bound was actually established in [103].

Theorem 62

For positive integers m and n,

$$\chi _{_{=}}^{{\ast}}(K_{ m} \times K_{n}) \leq \left \lceil \frac{mn} {\min \{m,n\} + 1}\right \rceil.$$

As to exact values, the following were established in [31] and [54], respectively:

• 1. $\chi _{_{=}}(C_{m}\times C_{n}) =\chi _{ _{=}}^{{\ast}}(C_{m}\times C_{n}) = \left \{\begin{array}{ll} 2&\mbox{ if }m\,n\,\text{is even},\\ 3 &\mbox{ otherwise.}\end{array} \right.$

• 2. $\chi _{_{=}}(P_{m}\times K_{1,n}) = \left \{\begin{array}{ll} 2&\mbox{ if }\ m\,\text{is\,even\,or}\,n = 1,\\ 3 &\mbox{ otherwise.}\end{array} \right.$

Lin in his Ph.D. dissertation [103] determined more exact values. They are listed as follows. Also see [104].

• 1. $\chi (P_{m} \times K_{2}) =\chi _{_{=}}(P_{m} \times K_{2}) =\chi _{ _{=}}^{{\ast}}(P_{m} \times K_{2}) = 2$, where $m \geq 2$.

• 2. $\chi (P_{2m+1} \times K_{n}) = 2 <\chi _{_{=}}(P_{2m+1} \times K_{n}) =\chi _{ _{=}}^{{\ast}}(P_{2m+1} \times K_{n}) = 3$, where n ≥ 3, except $\chi _{_{=}}^{{\ast}}(P_{3} \times K_{n}) =\max \left \{\left \lceil \frac{3} {2}\left \lceil \frac{2n} {s} \right \rceil \right \rceil \mid s \nmid 2n\mbox{ and }\left \lceil \frac{3} {2}\left \lceil \frac{2n} {s} \right \rceil \right \rceil \leq \left \lceil \frac{3n} {4} \right \rceil \right \}$.

• 3. $\chi (P_{2m} \times K_{n}) =\chi _{_{=}}(P_{2m} \times K_{n}) =\chi _{ _{=}}^{{\ast}}(P_{2m} \times K_{n}) = 2$, where m > 1 and n ≥ 3.

• 4. $\chi _{_{=}}^{{\ast}}(P_{2} \times K_{n}) =\max \left \{2\left \lceil \frac{n} {s} \right \rceil \mid s \nmid n\mbox{ and }2\left \lceil \frac{n} {2} \right \rceil \leq \left \lceil \frac{2n} {3} \right \rceil \right \}$, where n ≥ 3.

• 5. $\chi (C_{m} \times K_{2}) =\chi _{_{=}}(C_{m} \times K_{2}) =\chi _{ _{=}}^{{\ast}}(C_{m} \times K_{2}) = 2$, where m ≥ 3.

• 6. $\chi (C_{2m+1} \times K_{n}) =\chi _{_{=}}(C_{2m+1} \times K_{n}) =\chi _{ _{=}}^{{\ast}}(C_{2m+1} \times K_{n}) = 3$, where m > 1 and n ≥ 3, except $\chi _{_{=}}(C_{5} \times K_{n}) =\chi _{ _{=}}^{{\ast}}(C_{5} \times K_{n}) = 4$, when n ≥ 5.

• 7. $\chi _{_{=}}^{{\ast}}(C_{3}\,\times \,K_{n}) = \left \{\begin{array}{ll} \left \lceil \frac{3n} {4} \right \rceil &\mbox{ if }n\chi _{_{=}}\equiv 2 ({\rm mod} 4), \\ \max \{3\left \lceil \frac{n} {s} \right \rceil \mid s \nmid n\mbox{ and }3\left \lceil \frac{n} {s} \right \rceil \leq \left \lceil \frac{3n} {4} \right \rceil \}&\mbox{ otherwise,}\end{array} \right \}$ where n ≥ 3.

• 8. $\chi (C_{2m} \times K_{n}) =\chi _{_{=}}(C_{2m} \times K_{n}) =\chi _{ _{=}}^{{\ast}}(C_{2m} \times K_{n}) = 2$, where m > 1 and n ≥ 3.

• 9. $\chi _{_{=}}^{{\ast}}(C_{4} \times K_{n}) =\max \left \{2\left \lceil \frac{2n} {s} \right \rceil \mid s \nmid 2n\mbox{ and }2\left \lceil \frac{2n} {s} \right \rceil \leq \left \lceil \frac{4n} {5} \right \rceil \right \}$, where n ≥ 3.

• 10. $\chi _{_{=}}(K_{m_{1},n_{1}},K_{m_{2},n_{2}}) =\chi _{ _{=}}^{{\ast}}(K_{m_{1},n_{1}},K_{m_{2},n_{2}}) =\min \left \{\left \lceil \frac{n_{1}} {m_{1}} \right \rceil,\left \lceil \frac{n_{2}} {m_{2}} \right \rceil \right \} + 1$, where m ₁ ≤ n ₁ and m ₂ ≤ n ₂.

13.3 Strong Product

The upper bound for the inequality $\chi (G_{1} \boxtimes G_{2}) \leq \chi (G_{1})\chi (G_{2})$ is exact when both factors are complete graphs. As to lower bounds, there are those established by Vesztergombi [141] and Jha [74], respectively.

Theorem 63

For nontrivial graphs G ₁ and G ₂, $\chi (G_{1} \boxtimes G_{2}) \geq \max \{\chi (G_{1}),\chi (G_{2})\} + 2$.

Theorem 64

For nontrivial graphs G ₁ and G ₂, $\chi (G_{1} \boxtimes G_{2}) \geq \chi (G_{1}) +\omega (G_{2})$, where ω(G) denotes the clique number of the graph G, i.e., the largest order of a complete subgraph in G.

Furmańczyk [54] first investigated the equitable chromatic number of a strong product. Her results have been subsumed by those in [103]. Again, Lin’s results are listed as follows:

• 1. $\chi (C_{m} \boxtimes K_{n}) =\chi _{_{=}}(C_{m} \boxtimes K_{n}) =\chi _{ _{=}}^{{\ast}}(C_{m} \boxtimes K_{n}) = \left \lceil \frac{mn} {\left \lfloor m/2\right \rfloor }\right \rceil$, where m ≥ 3 and n ≥ 2.

• 2. $\chi (P_{m} \boxtimes K_{n}) =\chi _{_{=}}(P_{m} \boxtimes K_{n}) =\chi _{ _{=}}^{{\ast}}(P_{m} \boxtimes K_{n}) = 2n$, where m ≥ 2 and n ≥ 2.

• 3. $\chi (C_{m}\boxtimes C_{n}) =\chi _{_{=}}(C_{m}\boxtimes C_{n}) =\chi _{ _{=}}^{{\ast}}(C_{m}\boxtimes C_{n}) = \left \{\begin{array}{ll} 4&\mbox{ if }m\,\text{and}\,n\,\text{are even},\\ 5 &\mbox{ otherwise,}\end{array} \right \}$ where m, n ≥ 4.

• 4. $\chi (C_{m}\boxtimes P_{n}) =\chi _{_{=}}(C_{m}\boxtimes P_{n}) =\chi _{ _{=}}^{{\ast}}(C_{m}\boxtimes P_{n}) = \left \{\begin{array}{ll} 4&\mbox{ if }\ m\mbox{ is even,}\\ 5 &\mbox{ otherwise,}\end{array} \right \}$ where m ≥ 4 and n ≥ 3.

• 5. $\chi (P_{m}\boxtimes P_{n}) =\chi _{_{=}}(P_{m}\boxtimes P_{n}) =\chi _{ _{=}}^{{\ast}}(P_{m}\boxtimes P_{n}) = \left \{\begin{array}{ll} 4&\mbox{ if }\ m\,n\,\text{is even},\\ 5 &\mbox{ otherwise,}\end{array} \right \}$ where m ≥ 3 and n ≥ 3.

Conjecture 14

Suppose that G ₁ has at least one edge. Then $\chi _{_{=}}(G_{1} \boxtimes G_{2}) \geq \chi _{_{=}}(G_{1}) + 2\omega (G_{2}) - 2$ and $\chi _{_{=}}^{{\ast}}(G_{1} \boxtimes G_{2}) \geq \chi _{_{=}}^{{\ast}}(G_{1}) + 2\omega (G_{2}) - 2$.

The conclusions of the above conjecture hold if the equitable chromatic number of threshold is replaced by the ordinary chromatic number [103].

14 List Equitable Coloring

A mapping L is said to be a list assignment for the graph G if it assigns a finite list L(v) of possible colors, usually regarded as positive integers, to each vertex v of G. A list assignment L for G is k-uniform if | L(v) | = k for all v ∈ V (G). If G has a proper coloring π such that π(v) ∈ L(v) for all vertices v, then G is said to be L-colorable or π is an L-coloring of G. The graph G is said to be k-choosable if it is L-colorable for every k-uniform list assignment L, equitably L-colorable if it has a ⌈ | G | ∕ k⌉-bounded L-coloring for a k-uniform list assignment L, and equitably list k-colorable or equitably k-choosable if it is equitably L-colorable for every k-uniform list assignment L.

The concept of list-coloring was introduced by Vizing [144] and independently by Erdős et al. [45]. However, it is not appropriate to generalize the ordinary equitable coloring to this list context. To see this, let every vertex except one of a graph G be assigned the list [k] and the remaining vertex v be assigned the list [k + 1, 2k]. Unless | G | ≤ k + 1, in every proper coloring, some colors are not used, the color on v appears once, and some other color appears at least ⌈( | G | − 1) ∕ k⌉ times. This explains why the list version of an equitable coloring is defined in terms of boundedness of color classes. This notion was first introduced by Kostochka et al. [94], and they proposed two conjectures that are analogue to the Hajnál-Szemerédi Theorem and the EΔCC.

Conjecture 15

Every graph G is equitably k-choosable whenever k > Δ(G).

Conjecture 16

If G is a connected graph with maximum degree at least 3, then G is equitably Δ(G)- choosable, unless G is a complete graph or is K _{r, r} for some odd  r.

When Δ(G) = 2, it is easy to see the validity of Conjecture 16. Conjecture 15 has been proved for Δ(G) ≤ 3 independently by Pelsmajer [122] and Wang and Lih [146]. In [122], a graph G was shown to be equitably k-choosable when $k \geq 2 + \Delta (G)(\Delta (G) - 1)/2$. In [94], Kostochka et al. gave the following partial results to Conjecture 15 and 16:

Theorem 65

If $k \geq \max \{ \Delta (G),\vert G\vert /2\}$, then G is equitably k-choosable unless G contains K _k+1 or K _k,k (with k odd in the latter case).

Theorem 66

If G is a forest and k ≥ Δ(G)∕2 + 1, then G is equitably k-choosable. Moreover, for all m there is a tree with maximum degree at most m that is not equitable ⌈m∕2⌉-choosable.

Theorem 67

If G is a connected interval graph and k ≥ Δ(G), then G is equitably k-choosable unless G = K _k+1.

Theorem 68

If G is a 2-degenerate graph and $k \geq \max \{ \Delta (G),5\}$, then G is equitably k-choosable.

Pelsmajer [123] provided more partial results.

Theorem 69

Let G be a graph with treewidth w and k ≥ 3w − 1. Then G is equitably k-choosable if:

• 1. w ≤ 5 and k ≥ Δ(G) + 1, or

• 2. w ≥ 5 and k ≥ Δ(G) + w − 4.

A graph is said to be chordal if it has no induced cycle of length greater than three.

Corollary 12

Let G be a chordal graph with maximum degree at most Δ. Then G is equitably k-choosable for $k \geq \max \{ 3\Delta - 4,\Delta + 1\}$.

If vertices of degree 1 are removed recursively from a graph G, then the final graph has no vertices of degree 1 and is called the core of G. A graph is called a θ _2,2,p-graph if it consists of two vertices x and y and three internally disjoint paths of lengths 2, 2, and p joining x and y. Erdős et al. [45] characterized 2-choosable graphs in terms of these concepts. Analogous to their result, Wang and Lih [146] gave the following characterization:

Theorem 70

A connected graph G is equitably 2-choosable if and only if G is a bipartite graph satisfying the following two conditions:

• 1. The core of G is either a K ₁, an even cycle, or a θ _2,2,2r-graph, where r ≥ 1.

• 2. G has two parts X and Y such that $\vert \vert X\vert -\vert Y \vert \vert \leq 1$.

Bu and his collaborators have established a series of partial results for Conjecture 15 and 16 in the class of planar graphs as follows [100, 162, 163]:

Theorem 71

Let G be a C ₄ -free and C ₆ -free planar graph. Then G is equitably k-choosable when $k \geq \max \{ \Delta (G),6\}$.

Theorem 72

Let G be a C ₃ -free planar graph. Then G is equitably k-choosable when $k \geq \max \{ \Delta (G),8\}$.

Theorem 73

Let G be a C ₄ -free and C ₅ -free planar graph. Then G is equitably k-choosable when $k \geq \max \{ \Delta (G),7\}$.

Theorem 74

Let G be an outerplanar graph. Then G is equitably k-choosable when $k \geq \max \{ \Delta (G),4\}$.

Theorem 75

Let G be an outerplanar graph of maximum degree 3. Then G is equitably 3-choosable.

Recently, Theorems 74 and 75 have been generalized to series-parallel graphs by Zhang and Wu [159]. The following result confirms Conjecture 15 and 16 for series-parallel graphs:

Theorem 76

If G is a series-parallel graph with Δ(G) ≥ 3, then G is equitably k-choosable if $k \geq \Delta (G)$.

In the framework of parameterized complexity, the list equitable coloring problem was shown by Fellow et al. [47] to be $\mathcal{W}[1]$-hard even for forests, parameterized by the number of colors on the lists.

15 Graph Packing

The equitable coloring problem can be stated in the language of graph packing; hence it can be studied in a wider context. Two graphs G ₁ and G ₂ of the same order are said to pack if G ₁ is isomorphic to a subgraph of the complement G ₂ ^c of G ₂, or, equivalently, G ₂ is isomorphic to a subgraph of the complement $G_{1}^{c}$ of G ₁. This definition may be extended to n graphs G ₁, G ₂, …, G _n of the same order so that they pack if every pair of them pack:

Because the problem of whether G ^c packs with the cycle C _{| G |} is equivalent to the existence of a Hamiltonian cycle in G, two well-known sufficient conditions for the existence of a Hamiltonian cycle, due to Dirac [40] and Ore [121], can be cast in terms of graph packings.

Theorem 77

If Δ(G) ≤|G|∕2 − 1, then G packs with C _|G|.

Theorem 78

If deg (u) + deg (v) ≤|G|− 2 for every edge uv in G, then G packs with C _|G|.

A graph G is k-colorable if and only if G packs with a graph of the same order that is the union of k-cliques. Let H(n, k) denote the graph of order n such that it has k components each of which is a clique of order ⌊n ∕ k⌋ or ⌈n ∕ k⌉. This graph is the complement of the well-known Turán graph in extremal graph theory. A graph G is equitably k-colorable if and only if G packs with H( | G |, k). The Brooks’ Theorem and the Hajnal and Szemerédi Theorem can now be stated as follows:

Theorem 79

If r ≥ 3, G is a connected graph with Δ(G) ≤ r and G does not pack with the complement of any r-partite graph, then G = K _r+1.

Theorem 80

Let G satisfy Δ(G) ≤ r. Then G packs with H(|G|,r + 1).

In view of Ore’s theorem, the Ore degree of an edge uv, denoted by θ(uv), is defined to be deg(u) + deg(v), and the Ore degree of a graphG is θ(G) = max{θ(uv)∣uv ∈ E(G)}. Following [81], those upper bounds in terms of Ore degree giving sufficient conditions for packing graphs are called Ore-type bounds. Those in terms of maximum degree are called Dirac type.

An obvious Dirac-type bound on the chromatic number of a graph G is χ(G) ≤ Δ(G) + 1. The Brooks’ Theorem characterizes the conditions for equality to hold: either G contains K _{Δ(G) + 1} or Δ(G) = 2 and G contains an odd cycle. An Ore-type bound on χ(G) can be obtained easily such that $\chi (G) \leq \lfloor \theta (G)/2\rfloor + 1$. The bound is also attained at complete graphs. However, for small odd θ(G), there are more connected extremal graphs.

Theorem 81

If 6 ≤ k = χ(G) = ⌊θ(G) ∕2⌋ + 1, then G contains K _k.

Kierstead and Kostochka [83] proposed the above as a conjecture and proved the statement when the lower bound 6 was replaced by 7. The theorem has been established recently by Rabern [127]. See [96] for further generalizations. The above theorem can be equivalently stated as follows: for k ≥ 6, K _k is the only k-critical graph with maximum degree at most k whose vertices of degree k form an independent set. A k-critical graph is one that has chromatic number k, and any of its proper subgraphs has chromatic number less than k.

The bound 6 is sharp as Fig. 1 gives a graph G with θ(G) = 9 and χ(G) = 5. This graph is adapted from [83]. Note that every 4-coloring of the subgraph induced by x and y and the upper three vertices assigns x and y the same color since the upper three vertices form a K ₃. On the other hand, every 4-coloring of the subgraph induced by x and y and the lower four vertices assigns x and y different colors since the lower four vertices form a K ₄. It follows that χ(G) > 4.

Fig. 1

The graph G with θ(G) = 9 and χ(G) = 5

Kierstead and Kostochka also constructed infinite families of connected graphs H with θ(H) ≤ 7 and χ(H) = 4. Let G be a graph with θ(G) ≤ 7 and χ(G) = 4. An example for such a graph G is illustrated in Fig. 2a. A graph G′ with θ(G′) ≤ 7 and χ(G′) = 4 can be constructed as follows. Choose a vertex v of G that has no neighbor of degree 4. Split v into two vertices v ₁ and v ₂ of degree at most two. Add two new adjacent vertices x _v and y _v , each of which is joined to both v ₁ and v ₂. In this example, G′ is depicted in Fig. 2b. By construction, θ(G′) = 7. Since v ₁ and v ₂ are adjacent to x _v and y _v , any 3-coloring of G′ will assign the same color to v ₁ and v ₂. But then a 3-coloring of G can be produced, contrary to the assumption χ(G) = 4.

Fig. 2

A transformation from G to G′

Kierstead and Kostochka [81] proved a generalization of the Hajnal and Szemerédi Theorem involving the Ore degree.

Theorem 82

For every r ≥ 3, each graph G with θ(G) ≤ 2r + 1 has an equitable (r + 1)-coloring.

This implies that the EΔCC holds for graphs in which vertices of maximum degree form an independent set. In addition to K _{r + 1}, the extremal graphs for the above theorem are K _{m, 2r − m} for every odd 0 < m ≤ r. The following Ore-type analogue of the EΔCC was also proposed in [81] and, its truth for r = 3 was established.

Conjecture 17

Let r ≥ 3 and G be a connected graph with θ(G) ≤ 2r. If G differs from K _{r + 1} and K _{m, 2r − m} for all odd m, then G is equitably r-colorable.

A conjecture in the flavor of Conjecture 15 was proposed in [86], and positive evidence was provided for small θ.

Conjecture 18

Every graph G is equitably (⌈θ(G) ∕ 2⌉ + 1)-choosable.

Theorem 83

If θ(G) ≤ 6, then G is equitably 4-choosable.

In the graph packing area, a major outstanding conjecture was made independently by Bollobás and Eldridge [15] and Catlin [20, 21].

Conjecture 19

Let G ₁ and G ₂ be two graphs of the same order n. If (Δ(G ₁) + 1) (Δ(G ₂) + 1) ≤ n + 1, then G ₁ and G ₂ pack.

The Hajnal-Szemerédi Theorem verifies the conjecture in the case when G ₂ is the disjoint union of copies of a clique. Aigner and Brandt [1] and independently (for huge n) Alon and Fischer [4] settled the case Δ(G ₁) ≤ 2. Csaba et al. [36] proved the case for Δ(G ₁) = 3 and huge n. Bollobas et al. [17] proved it in case that for d ≥ 2, G ₁ is d-degenerate, Δ(G ₁) ≥ 40d, and Δ(G ₂) ≥ 215. Kaul et al. [86] showed that for Δ(G ₁), Δ(G ₂) ≥ 300, if (Δ(G ₁) + 1)(Δ(G ₂) + 1) < 3n ∕ 5, then G ₁ and G ₂ pack. Recently, Kun has announced a proof of the conjecture for graphs with at least 10⁸ vertices.

The reader is referred to Wozniak [151] for a general survey on the graph packing area and to Kierstead et al. [79] for recent progress in Ore-type and Dirac-type bounds for graph packing problems.

16 Equitable Δ-Colorabilityof Disconnected Graphs

If a disconnected graph G is Δ(G)-colorable, then the conditions for G to be equitably Δ(G)-colorable are quite different. For an odd integer r ≥ 3, G is equitably Δ(G)-colorable if G = K _{r, r} ∪K _{r, r} . However, G is not equitably Δ(G)-colorable if G = K _{r, r} ∪K _r . The latter example can be generalized. A graph H is said to be r-equitable if r divides | H |, H is r-colorable, and every r-coloring of H is equitable. For an odd integer r ≥ 3, if H = K _{r, r} is a subgraph of G and G − H is r-equitable, then G is not equitably r-colorable. Kierstead and Kostochka [84] gave a good description of the family of all r-equitable graphs so that all of them can be built up from simple examples in a straightforward way. Their approach to deal with disconnected graphs led them to propose the following conjecture.

Conjecture 20

Suppose that Δ(G) = r ≥ 3 and G is an r -colorable graph. Then G is not equitably r -colorable if and only if the following conditions hold:

• 1. r is odd.

• 2. G has a subgraph H = K _{r, r} .

• 3. G − H is r-equitable.

Chen and Yen [27] have also found sufficient conditions for the nonexistence of equitable Δ-colorings for graphs that are not necessarily connected.

Theorem 84

Suppose that Δ(G) = r ≥ 3 and G is an r-colorable graph. Then G is not equitably r-colorable if the following conditions hold:

• 1. r is odd.

• 2. G has exactly one component H = K _r,r.

• 3. α(G − H) ≤|G − H|∕r.

Suppose that Δ(G) = r and G is an r-colorable graph such that G has exactly one K _{r, r} component. If G = K _{r, r} , then $\alpha (G - K_{r,r}) = 0 = \vert G - K_{r,r}\vert /r$. Otherwise, $\alpha (G - K_{r,r}) \geq \vert G - K_{r,r}\vert /\chi (G - K_{r,r}) \geq \vert G - K_{r,r}\vert /\chi (G) \geq \vert G - K_{r,r}\vert /r$. Hence, Condition 3 can be replaced by an equality. Chen and Yen conjectured that those sufficient conditions are also necessary and established some positive evidence.

Conjecture 21

Suppose that Δ(G) = r ≥ 3 and G is an r -colorable graph. Then G is not equitably r -colorable if and only if the following conditions hold:

• 1. r is odd.

• 2. G has exactly one component H = K _{r, r} .

• 3. α(G − H) = | G − H | ∕ r.

Theorem 85

A bipartite graph G satisfying Δ(G) ≥ 2 is equitably Δ(G)-colorable if and only if G is different from K _r,r for all odd r ≥ 3.

Theorem 86

A graph G that is Δ(G)-colorable and satisfies Δ(G) ≥ 1 + |G|∕3 is equitably Δ(G)-colorable if and only if G is different from K _r,r for all odd r ≥ 3.

Theorem 87

Conjecture 21 holds for Δ(G) = 3.

It was shown in Chen et al. [32] that Conjecture 20 and 21 are in fact equivalent. The proof utilizes the following result that was established in Chen et al. [30].

Theorem 88

Let $r \geq \chi (G) \geq \Delta (G)$. Then there exists a proper coloring of G using r colors such that some color class has size α(G).

Further lemmas are needed in the equivalence proof.

Lemma 7

If G is r-colorable and α(G) = |G|∕r, then G is r-equitable.

Lemma 8

If G is r-equitable, then r = χ(G).

Lemma 9

Let r ≥ Δ(G). If G is r-equitable, then α(G) = |G|∕r.

By Lemma 8, χ(G) = r ≥ Δ(G). By Theorem 88, there exists an r-coloring ϕ of G such that a color class of ϕ is of size α(G). Since G is r-equitable, ϕ is an equitable r-coloring and r divides | G|. Hence α(G) = | G | ∕ r.

Lemma 10

Let a graph G satisfy Δ(G) = r ≥ 3. If G is r-equitable, then G does not have K _r,r as a subgraph.

Suppose on the contrary that G has a subgraph H = K _{r, r} . The subgraph H is a component of G since r = Δ(G). Hence, $\vert G\vert = \vert G - H\vert + \vert H\vert = \vert G - H\vert + 2r$ and $\alpha (G) =\alpha (G - H) +\alpha (H) =\alpha (G - H) + r$. By Lemma 9, $\alpha (G) = \vert G\vert /r = \vert G - H\vert /r + 2$. Therefore, $\alpha (G - H) = \vert G - H\vert /r + 2 - r \leq \vert G - H\vert /r - 1$. On the other hand, Lemma 8 implies r = χ(G) ≥ χ(G − H). Then $\alpha (G - H) \geq \lceil \vert G - H\vert /\chi (G - H)\rceil \geq \lceil \vert G - H\vert /r\rceil \geq \vert G - H\vert /r$. A contradiction is obtained.

Lemma 11

Let a graph G satisfy Δ(G) = r ≥ χ(G). If r ≥ 3, G has a subgraph H = K _r,r , and G − H is r-equitable, then G has exactly one K _r,r component.

If $G = K_{r,r}$ or Δ(G − H) < r, then G has exactly one K _{r, r} component H. Now, suppose that G≠K _{r, r} and Δ(G − H) = r. Since r ≥ 3 and G − H is r-equitable, G − H does not have K _{r, r} as a subgraph by Lemma 10. Therefore, G has exactly one K _{r, r} component H.

Using Lemmas 7, 9, and 11, the equivalence of two conjectures follows.

Theorem 89

Conjecture 20 and 21 are equivalent.

In [84], Kierstead and Kostochka described their conjecture in terms of other equivalent conditions. An r-equitable graph G is said to be r-reducible if V (G) has a partition {V ₁, …, V _t } into at least two parts such that all induced subgraphs G[V _i ] are r-equitable. If such a partition fails to exist, then G is called r-irreducible. Obviously, K _r is r-irreducible. It can be identified that there is one other 5-irreducible graph F ₁ (Fig. 3), three other 4-irreducible graphs F ₂, F ₃, F ₄ (Fig. 4), and six other 3-irreducible graphs F ₅, …, F ₁₀ ( Figs. 5 and 6). Together with K _r , the r-irreducible graphs in the list F ₁, …, F ₁₀ are called r-basic graphs.

Fig. 3

The 5-irreducible graph F ₁

Fig. 4

The 4-irreducible graphs F ₂, F ₃, and F ₄

Fig. 5

The 3-irreducible graphs F ₅, F ₆, and F ₇

Fig. 6

The 3-irreducible graphs F ₈, F ₉, and F ₁₀

An r-decomposition of G is a partition {V ₁, …, V _t } of V (G) such that every induced subgraph G[V _i ] is r-basic. The graph G is called r-decomposable if it has an r-decomposition. A nearly equitable r-coloring of a graph G is an r-coloring of G such that exactly one color class has size s − 1, exactly one color class has size s + 1, and all other color classes have size s.

Let $\mathcal{G}(r)$ be the class of all graphs whose maximum degree and chromatic number are less than or equal to r. Let $\mathcal{G}(r,n)$ denote the subclass of $\mathcal{G}(r)$ consisting of all graphs of order at most n.

Theorem 90 ([84])

Let $G \in \mathcal{G}(r)$ and r divide |G|. Then the following are equivalent.

• 1. G is r-equitable.

• 2. G is r-decomposable.

• 3. G has an equitable r-coloring, but does not have a nearly equitable r-coloring.

Conjecture 20 can now be re-stated as follows.

Conjecture 22

Suppose that $\Delta (G) = r \geq 3$ and G is an r -colorable graph. Then G is not equitably r-colorable if and only if the following conditions hold.

• 1. r is odd.

• 2. G has a subgraph H = K _{r, r} .

• 3. G − H is r-decomposable.

For r ≥ 6, this conjecture means that, if an r-colorable graph G with Δ(G) = r has no equitable r-coloring, then r is odd and there exists a partition $V (G) = V _{0} \cup V _{1} \cup \cdots \cup V _{t}$ such that $G[V _{0}] = K_{r,r}$ and G[V _i ] = K _r for 1 ≤ i ≤ t. Theorem 90 can be used to derive the corollaries below.

Corollary 13

For all positive integers r and n > r, the EΔCC holds for all graphs in $\mathcal{G}(r,n)$ if and only if Conjecture 22 holds for all graphs in $\mathcal{G}(r,n)$.

Corollary 14

Let $G \in \mathcal{G}(r)$ be r-equitable. Then G has a unique r-decomposition.

Corollary 15

There exists a polynomial time algorithm for deciding whether a graph $G \in \mathcal{G}(r)$ is r-equitable.

The following conjecture proposed in [83] is a common extension of Conjecture 17 and 22.

Conjecture 23

Let r ≥ 3. An r-colorable graph G with θ(G) ≤ 2r has no equitable r-coloring if and only if r divides | G |, G has a subgraph H = K _{m, 2r − m} for some odd m, and G − H is r-decomposable.

This conjecture is proved to be equivalent to Conjecture 17 for graphs with restricted order and Ore-degree.

Theorem 91

Let r ≥ 3. Assume that Conjecture 17 holds for all graphs of order at most n and Ore-degree at most 2r. Let G be an r-colorable graph of order n with θ(G) ≤ 2r. Then G has no equitable r-coloring if and only if r divides n, G has a subgraph H = K _m,2r−m for some odd m, and G − H is r-decomposable.

It follows that Conjecture 23 holds for r = 3.

17 More on the Hajnal-Szemerédi Theorem

The Hajnal-Szemerédi Theorem settled a conjecture raised by Erdős in 1964. The complete proof given in [64] was long and complicate, and did not produce a polynomial time algorithm. A simplification came when Kierstead and Kostochka [82] used a discharging argument in an approach similar to the original one. An analysis of their proof leads to a complexity results.

Theorem 92

There is an algorithm of time complexity O(n ⁵) that constructs an equitable (r + 1)-coloring of any graph G with |G| = n and Δ(G) ≤ r.

An even shorter proof of the Hajnal-Szemerédi Theorem was included in the survey paper [86]. Independent of Kierstead and Kostochka, Mydlarz and Szemerédi also found polynomial time algorithm proof for the Hajnal-Szemerédi Theorem. These two groups finally worked together to refine their old methods and arrived at a faster algorithm [87].

Theorem 93

There is an algorithm of time complexity O(rn ²) that constructs an equitable (r + 1)-coloring of any graph G with |G| = n and Δ(G) ≤ r.

However, the existence of an algorithmic version of Theorem 82 is still open.

Conjecture 24

There is a polynomial time algorithm that constructs an equitable (r + 1)-coloring of any graph G with θ(G) ≤ 2r + 1.

When one pays attention to the complement of the graph given in the Hajnal-Szemerédi Theorem, the theorem can be stated in the following form of which the first non-trivial case r = 3 had previously been solved by Corrádi and Hajnal [34].

Theorem 94

Let G be a graph of order n with the minimum degree $\delta (G) \geq \frac{r-1} {r} n$. If r divides n, then G contains n∕r vertex-disjoint cliques of size r.

In order to extend the above to a multipartite version, the next conjecture was proposed in Csaba and Mydlarz [35]. If all parts of an r-partite graph G have the same size, then G is called a balanced r-partite graph. Let V ₁, V ₂, …, V _r be the parts of such a graph G. The proportional minimum degree of G is defined as follows.

$$\tilde{\delta }(G) =\min _{1\leq i\leq r}\min _{v\in V _{i}}\left \{\frac{\deg (v,V _{j})} {\vert V _{j}\vert } \mid j\neq i\right \}.$$

Conjecture 25

Let G be a balanced r-partite graph of order rn. There exists a constant M ≥ 0 such that, if $\tilde{\delta }(G)n \geq \frac{r-1} {r} n + M$, then G contains n vertex-disjoint cliques of size r.

The extra additive constant M is necessary for the case of odd r. Partial results have been obtained by Fischer [50] and Johansson [75]. The conjecture has been confirmed for r = 3 [109] and r = 4 [111]. In [35], Csaba and Mydlarz proved a relaxed version of this conjecture. The proofs commonly used Szemerédi’s Regularity Lemma [136] and the Blow-up Lemma [88] and are complicate. The cases for r = 3 and r = 4 have been reproved by Han and Zhao [65] using their absorbing method. The paper [80] by Keevash and Mycroft contains results about multipartite graphs with sufficiently large girth. Recently, Conjecture 25 has been verified asymptotically by Lo and Markström [106]. Balogh et al. [8] extended the result of Corrádi and Hajnal into the setting of sparse random graphs.

In order to find a understandable proof of the Hajnal-Szemerédi Theorem, Seymour [132] was motivated to pose the following conjecture. The r-th power of a graph is obtained by adding new edges joining vertices with distance at most r.

Conjecture 26

Let G be a graph of order n with $\delta (G) \geq \frac{r} {r+1}n$. Then G contains the r-th power of C _n .

Theorem 77 is the case r = 1. The well-known Posa’s conjecture (cf. [43]) is the case r = 2. Seymour’s conjecture implies the Hajnal-Szemerédi Theorem since any r + 1 consecutive vertices of the r-th power of a cycle induce K _{r + 1}. Seymour’s conjecture has been proved by Komolós et al. [89, 90] when the order of the graph is extremely large using Szemerédi’s Regularity Lemma and the Blow-up Lemma.

Theorem 95

For every positive integer r, there exists an integer N such that for every n > N every graph G of order n with $\delta (G) \geq \frac{r} {r+1}n$ contains the r-th power of a hamiltonian cycle.

18 Applications

Graph coloring can be regarded as a partition of resources problem. It is convenient in some situations to require color classes be of approximately the same size. Graph coloring is also a natural model for scheduling problems. Suppose that a number of jobs are given to be completed. A conflict graph can be constructed so that vertices represent jobs and two vertices are adjacent if there is a scheduling conflict between the jobs associated with these vertices. A proper coloring of the conflict graph corresponds to a conflict-free schedule. Some other examples are listed below.

• 1. The mutual exclusion scheduling problem [7, 134].

• 2. Scheduling in communication systems [70].

• 3. Round-the-clock scheduling [138].

• 4. Parallel memory systems [11, 37].

• 5. Load balancing in task scheduling [11, 97].

• 6. Constructing university timetables [55].

In applications, only algorithms with low time complexity could be utilized. Although checking $\chi _{_{=}}(G) \leq 2$ can be achieved in polynomial time, the problem of deciding if $\chi _{_{ =}}(G) \leq 3$ is NP-complete even for line graphs of cubic graphs. The majority of known polynomial time results about equitable coloring are listed in [53] and [55]. Two competitive algorithms for approximate equitable coloring were also supplied. In [112, 113], and [114], Méndez-Díaz et al. gave a linear integer programming formulation for the equitable coloring problem. They studied its polyhedral structure and developed a cutting plane algorithm. Experiments on randomly generated graphs have been performed to make behavior comparisons with other algorithms of similar nature. Bahiense et al. [6] also gave two integer programming formulations based on representatives for the equitable coloring problem. They proposed a primal constructive heuristic, branching strategies, and branch-and-cut algorithms based on these formulations. Computational experiments were carried out on randomly generated graphs.

Applications of equitable colorings to other mathematical problems include the following.

Alon and Füredi [5] used equitable colorings to the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random graphs.

Rödl and Ruciński [128] used equitable colorings to give a new proof of the Blow-Up Lemma.

Let $\mathcal{X} =\{ X_{1},X_{2},\ldots,X_{n}\}$ be a collection of random variables with $S =\sum _{i\in [n]}X_{i}$ and μ = E[S]. The upper tail probability Prob[ $S \geq (1+\epsilon )\mu$] and the lower tail probability Prob[ $S \leq (1-\epsilon )\mu$] for 0 < ε ≤ 1 are subjects of interest. A dependency graph for $\mathcal{X}$ has vertex set [n] and an edge set such that for each i ∈ [n], X _i is mutually independent of all other X _j with j non-adjacent to i. In Pemmaraju [124], it is shown that a small equitable chromatic number for a dependency graph leads to sharp tail probability bounds that are roughly as good as those would have been obtained had the random variables been mutually independent. An example is an outerplanar dependency graph and Theorem 23 plays an important role in the proof.

Pemmaraju also introduced an interesting notion of proportional coloring. For non-negative integer c and integer α ≥ 1, a proper coloring of G is said to be a (c,α)-coloring if all except at most c vertices are colored and $\vert V _{i}\vert \leq \alpha \vert V _{j}\vert$ for any pair of color classes V _i and V _j . Theorem 1 can be extended to show that every tree has a (1, 5)-coloring with two colors and every outerplanar graph has a (2, 5)-coloring with four colors. Sharp tail probability bounds can be established if the dependency graph can be (c, α)-colored [124].

Pemmaraju believed that $\chi _{_{=}}(G)$ should depend on the average degree rather than on the maximum degree and he proposed the conjecture below.

Conjecture 27

There is a positive constant c such that, if a graph G has maximum degree at most | G | ∕ c and average degree d, then $\chi _{_{=}}(G) = O(\chi (G) + d)$.

The truth of this conjecture will immediately imply an O(1) equitable chromatic number for most planar graphs and that will translate into extremely sharp tail probability bounds for the sum of random variables that have a planar dependency graph.

Janson et al. [71] and Janson and Ruciński [72] also used equitable colorings to get new bounds on tails of distributions of sums of random variables.

19 Related Notions of Coloring

In this section, some coloring notions related to equitable coloring will be discussed.

19.1 Equitable Edge-Coloring

An edge-coloring of a graph G is simply an assignment of colors to the edges of G. An edge-k-coloring of G assigns the k colors {1, 2, …, k} to the edges of G. For a vertex v of G, let c _i (v) denote the number of edges incident with v colored i. This edge-k-coloring is said to be equitable if, for each vertex v,

$$\vert c_{i}(v) - c_{j}(v)\vert \leq 1\quad (1 \leq i < j \leq k)$$

and nearly equitable if, for each vertex v,

$$\vert c_{i}(v) - c_{j}(v)\vert \leq 2\quad (1 \leq i < j \leq k).$$

The following was proved in [68 ].

Theorem 96

If k ≥ 2 does not divide the degree of any vertex, then the graph has an equitable edge-k-coloring.

Hilton and de Werra made the observation at the end of their paper that the colorings can be so constructed that all color classes have equitable sizes.

An edge-coloring is said to be proper if any two edges are colored differently whenever they are incident to a common vertex. The smallest number of colors needed in a proper edge-coloring of G is called the chromatic index of G and denoted by χ′(G). Obviously, $\Delta (G) \leq \chi ^{\prime}(G)$. The above theorem reduces to the following well-known theorem of Vizing [142] when k = Δ(G) + 1.

Theorem 97

For any graph G, $\chi ^{\prime}(G) \leq \Delta (G) + 1$.

An edge cover coloring of a graph G is a coloring of the edges of G so that, for every vertex v, each color appears at least once on some edge incident to v. The maximum number of colors needed for such a coloring is called the edge cover chromatic index of G and denoted by $\chi _{c}^{\prime}(G)$. Let k = δ(G) + 1. Applying Theorem 96 to the graph obtained from G by adjoining a pendant edge to each vertex v whose degree is a multiple of k, the following result of Gupta [62] is deduced.

Theorem 98

For any graph G, $\delta (G) - 1 \leq \chi _{c}^{\prime}(G) \leq \delta (G)$.

Given k ≥ 2, the k-core of a graph G is the subgraph of G induced by all vertices v whose degree is a multiple of k. A stronger form for Theorem 96 also appeared in [68].

Theorem 99

Given k ≥ 2, if the k-core of G contains no edges, then G has an equitable edge-k-coloring.

The following recent result of Zhang and Liu [158] was first conjectured by Hilton and de Werra [68].

Theorem 100

Given k ≥ 2, if the k-core of G is a forest, then G has an equitable edge-k-coloring.

A graph G is called edge-equitable if G has an equitable edge-k-coloring for any integer k ≥ 2. If a graph is edge-equitable, then its chromatic index is equal to its maximum degree and its edge cover chromatic index is equal to its minimum degree. All bipartite graphs were shown to be edge-equitable in de Werra [38].

A circuit is a connected graph without any vertex of odd degree. A circuit is said to be odd, or even, according to its number of edges is odd, or even. It was stated in [38] that a connected graph has an equitable edge-2-coloring if and only if it is not an odd circuit. Wu [152] showed that a connected outerplanar graph is edge-equitable if and only if it is not an odd circuit. This can be generalized to series-parallel graphs. The following result was established by Song et al. [135].

Theorem 101

Any connected series-parallel graph is edge-equitable if and only if it is not an odd circuit.

Theorem 96 also has the following corollary.

Corollary 16

Let k ≥ 2. Then, for any graph G, there exists an edge-k-coloring of G such that, for each vertex v,

• 1. |c _i (v) − c _j (v)| = 2 for at most one pair {i,j} of colors, and

• 2. |c _s (v) − c _t (v)| ≤ 1 for all pairs {s,t} ≠ {i,j} of colors.

This can be proved by adjoining a pendant edge to each vertex of G whose degree is a multiple of k. Then apply Theorem 96 to this extended graph. The corresponding edge-coloring of G satisfies the above conditions. Thus, every graph has a nearly equitable edge-k-coloring for any given k ≥ 2. In fact, Corollary 16 is equivalent to Theorem 96. To see this, suppose that k does not divide the degree of any vertex of G and the conditions of Corollary 16 are satisfied. For each vertex v of G, since deg(v) is not a multiple of k, it is not possible to have $\vert c_{i}(v) - c_{j}(v)\vert = 2$ for one pair {i, j} of colors unless some second pair $\{s,t\}\neq \{i,j\}$ of colors satisfies | c _s (v) − c _t (v) | = 2 also. Thereby, an equitable edge-coloring with k colors can be produced.

For efficient algorithms for nearly equitable edge-coloring problem, the reader is referred to Shioura and Yagiura [133], Xie et al. [154], and references therein. These algorithms can produce color classes that have equitable sizes.

19.2 Equitable Total-Coloring

A total-k-coloring of a graph G = (V, E) is a mapping $f : V (G) \cup E(G) \rightarrow \{ 1,2,\ldots,k\}$ such that any two adjacent or incident elements have distinct images. The total chromatic numberχ′(G) is the smallest integer k such that G has a total-k-coloring. A total-k-coloring is said to be equitable if $\vert \vert {f}^{-1}(i)\vert -\vert {f}^{-1}(j)\vert \vert \leq 1$ when 1 ≤ i < j ≤ k. Fu [52] first studied equitable total-coloring under the name equalized total coloring and put forward the following tentative conjecture.

Conjecture 28

For each k ≥ χ′(G), there exists an equitable total-k-coloring of  G.

Fu proved this conjecture for complete graphs, complete bipartite graphs, trees, and complete split graph K _m ∨ I _n . However, the tentative conjecture does not hold in general. Fu gave a family of counterexamples.

Theorem 102

For any n ≥ 3, let $G = nK_{2} \vee I_{2n-1}$. Then χ′(G) = 2n + 1, yet G has no equitable total-(2n + 1)-coloring. However, G has an equitable total-k-coloring for any k ≥ 2n + 2 = Δ(G) + 2.

This theorem prompted Fu to make the following refined conjecture.

Conjecture 29

For each $k \geq \max \{\chi ^{\prime \prime}(G),\Delta (G) + 2\}$, G has an equitable total-k-coloring.

Fu also proved that G satisfies the above conjecture if Δ(G) = | G | − 2, or G is a complete multipartite graph of odd order. When G is a multipartite graph of even order, the best Fu could prove was that G has an equitable total-k-coloring for any k ≥ Δ(G) + 3. Wang [145] proposed the following weaker conjecture in which the equitable total chromatic index $\chi _{_{ =}}^{\prime \prime}(G)$ of a graph G is defined to be the least integer k such that G has an equitable total-k-coloring. Wang proved the conjecture holds for graphs G with Δ(G) ≤ 3.

Conjecture 30

For any graph G, $\chi _{_{ =}}^{\prime \prime}(G) \leq \Delta (G) + 2$.

This weaker conjecture is powerful enough to imply the outstanding Total Coloring Conjecture, proposed independently by Behzad [9] and Vizing [143], which asserts $\chi ^{\prime \prime}(G) \leq \Delta (G) + 2$ for any graph G.

For some classes of graphs, the upper bound in the above conjecture can be lowered to Δ(G) + 1. Chungling et al. [33] proved the following for the square product of cycles.

Theorem 103

Let $G = C_{m}\square C_{n}$. Then, for m ≥ 3 and n ≥ 3, $\chi _{_{ =}}^{\prime \prime}(G) = \Delta (G) + 1 = 5$.

The wheelW _n is defined to be the join of a cycle C _n with a center vertex u. The Mycielskian $\mathsf{M}(W_{n})$ of W _n is constructed as follows. For each vertex x of W _n , a new vertex x′ is added. Join x _i and $x_{j}^{\prime}$ with an edge whenever x _i and x _j are adjacent in W _n . Finally, add one more new vertex w and make it adjacent to every new vertices x′. The hypo-Mycielskian $\mathsf{HM}(W_{n})$ of W _n has the same vertex set as M(W _n ) and all edges of M(W _n ) except those of the form ux′, x≠u. Note that Δ(HM(W _n )) is equal to 6 when n = 3 or 4 and is equal to n + 1 when n ≥ 5.

Theorem 104 ([147])

For n ≥ 3, $\chi _{_{ =}}^{\prime \prime}(\mathsf{M}(W_{n})) = \Delta (G) + 1$.

Theorem 105 ([148])

For n ≥ 3, $\chi _{_{ =}}^{\prime \prime}(\mathsf{HM}(W_{n})) = \Delta (G) + 1$.

One question left open in [52] asks whether the existence of an equitable total-k-coloring implies that of an equitable total-(k + 1)-coloring.

19.3 Equitable Defective Coloring

A reasonable relaxation of scheduling problem allows conflicts to happen to a certain level. The graph coloring model corresponds to this type of relaxation can be formulated as follows. A d-defective coloring is a coloring of the vertices of a graph in which monochromatic subgraphs have maximum degree at most d. An ordinary proper coloring is precisely a 0-defective coloring. A defective coloring simply means a 1-defective coloring, in which a vertex may share a color with at most one neighbor. The smallest number k such that the graph G has a 1-defective coloring is denoted by df₁(G).

A graph G has an equitable defective k-coloring, or an ED-k-coloring, if G has a coloring using k colors that is both equitable and defective. This notion of coloring was introduced by Williams et al. [150]. Let $\chi _{_{\mathrm{ED}}}(G)$ denote the smallest integer k such that G has an ED-k-coloring, and $\chi _{_{\mathrm{ED}}}^{{\ast}}(G)$ the smallest integer k such that G has an ED-m-coloring for all m ≥ k. It is clear that df $_{1}(G) \leq \chi _{_{\mathrm{ED}}}^{{\ast}}(G) \leq \chi _{_{\mathrm{ED}}}(G)$. These parameters may differ from each other by an arbitrarily large amount. The following example was provided in [150]. Consider X = K _{⌈n ∕ 2⌉} and Y = I _{⌊n ∕ 2⌋}. Let G be the graph obtained from X ∨ Y by removing a matching between X and Y of size ⌊n ∕ 2⌋. Note that $\chi (G) =\chi _{ _{=}}^{{\ast}}(G) = \lceil n/2\rceil$. If X is colored with $\vert X\vert /2 = \lceil n/4\rceil$ colors and Y is colored with one extra color, then df₁(G) ≤ ⌈n ∕ 4⌉ + 1. If a color class in an ED-coloring contains two vertices of X, then it cannot contain any other vertices. This forces every color class has at most three vertices. However, color classes of size three must contain at least two vertices of Y. Therefore, there are at most | Y | ∕ 2 color classes of size three. It follows that $\chi _{_{\mathrm{ED}}}(G) \geq \lceil 3n/8\rceil$. It is easy to see that an ED-coloring with k colors exists for any k ≥ ⌈3n ∕ 8⌉, and hence $\chi _{_{\mathrm{ED}}}^{{\ast}}(G) = \lceil 3n/8\rceil$.

Extending results in [108], Williams et al. proved the following.

Theorem 106

If G is a planar graph with minimum degree δ(G) ≥ 2 and girth g(G) ≥ 10, then $\chi _{_{\mathrm{ED}}}^{{\ast}}(G) \leq 3$.

The condition δ(G) ≥ 2 is indispensable since K _{1, n} has no ED-k-coloring when n is sufficiently large for any fixed k. The girth condition cannot be lower than 5 since K _{2, n} has girth 4 but $\chi _{_{\mathrm{ED}}}^{{\ast}}(K_{2,n})$ is not bounded by any constant. Whether 5 is the smallest girth that a planar graph G can have so that $\chi _{_{\mathrm{ED}}}^{{\ast}}(G)$ can be bounded by a constant is an open question.

Recently, Fan et al. [46] have shown that a graph with maximum degree at most r admits an equitable ED-r-coloring and provided a polynomial-time algorithm for constructing such a coloring.

19.4 Equitable Coloring of Hypergraphs

A hypergraph $\mathcal{H}$, is an ordered pair $(V,\mathcal{F})$, where $\mathcal{F}$ is a family of subsets of the finite set V. Elements of V and $\mathcal{F}$ are called vertices and hyperedges of $\mathcal{H}$, respectively. The number of hyperedges incident with a vertex of $\mathcal{H}$ is called its degree. A hypergraph is said to be k-uniform if each hyperedge has precisely k-elements.

Let $\mathcal{H}$ be a k-uniform hypergraph on n vertices. A strong r-coloring of $\mathcal{H}$ is a partititon of the vertices into r parts, called color classes, such that each hyperedge intersects each part. A strong r-coloring is called equitable if the size of each color class is either ⌈n ∕ r⌉ of ⌊n ∕ r⌋. Let $c(\mathcal{H})$ and $ec(\mathcal{H})$ denote the maximum possible number of color classes in a strong coloring and an equitable coloring of $\mathcal{H}$, respectively. Clearly, $1 \leq ec(\mathcal{H}) \leq c(\mathcal{H}) \leq k$. If no upper bounds are imposed on the maximum degree, then $ec(\mathcal{H}) = c(\mathcal{H}) = 1$ could happen even k is large. An example is the complete k-uniform hypergraph on 2k vertices that satisfies $c(\mathcal{H}) = 1$ and maximum degree less than 4^k.

Let a ≥ 1 be any real number, and let ε > 0 be small. Let k be sufficiently large such that there exists an integer in the interval $[k/(1 {+\epsilon }^{2}/4)a\ln k,k/(1 {+\epsilon }^{2}/8)a\ln k]$. For some γ in the interval [ε ² ∕ 8, ε ² ∕ 4], the number k ∕ (1 + γ)alnk is an integer. Let $\mathcal{H}$ be a k-uniform hypergraph with maximum degree at most k ^a. Yuster [157] proved that there exists an equitable coloring of $\mathcal{H}$ with $k/(1+\gamma )a\ln k -\left \lceil k\sqrt{\gamma }/a\ln k\right \rceil> (1-\epsilon )k/a\ln k$ colors and the following was established.

Theorem 107

If a ≥ 1 and $\mathcal{H}$ is a k-uniform hypergraph with maximum degree at most k ^a, then $ec(\mathcal{H}) \geq \frac{k} {a\ln k}(1 - o_{k}(1))$. The lower bound is asymptotically tight. For all a ≥ 1, there exists k-uniform hypergraphs $\mathcal{H}$ with maximum degree at most k ^a and $c(\mathcal{H}) \leq \frac{k} {a\ln k}(1 + o_{k}(1))$.

Note that results in Alon [3] have already implied that no equitable coloring of a k-uniform hypergraph could have more than (k ∕ lnk)(1 + o _k (1)) color classes. Yuster made the following remarks at the end of his paper [157].

Using more involved computations, Theorem 107 can be proved when a is not a constant but satisfies a = a(k) = o(k ∕ lnk), i.e., the degree of $\mathcal{H}$ is allowed to be any subexponential function of k.

It is possible to convert the proof of Theorem 107 into an algorithmic one. In terms of the number of vertices of the hypergraph, but not in its uniformity, a polynomial time algorithm can be found to produce an equitable partition with (1 − o _k (1))ck ∕ (alnk) color classes, where c is a fixed small constant depending only on a.

A special case of Theorem 107 gives the following interesting result about graphs. Let G be a k-regular graph. If k is sufficiently large, then G has an equitable coloring with (1 − o _k (1))(k ∕ lnk) colors such that each color class is a so-called total dominating set, that is a subset of the vertices such that each vertex of G has a neighbor in that subset.

20 Conclusion

The subject of graph coloring occupies a central position in graph theory. Historically speaking, much of the early development of graph theory was motivated by the attempts at solving the four-color conjecture. Later on, a large number of variants or generalizations of graph coloring problem have emerged. Graph coloring involves deep mathematical and computational issues. The possibilities for applications are also wide. When resources are allocated, a certain kind of graph coloring model may be lurking around. The requirement for even distribution is rather natural. The equitable coloring goes to the extreme to make color classes differ in size by at most one. This may be too stringent for applications in the real world. Yet it brings up hard questions to be addressed.

Although the concept of an equitable coloring of a graph was introduced in early 1970s, substantial research results have only been accumulated in the last 20 years. The importance of the equitable Δ-coloring conjecture has gradually been recognized. Positive evidence has been collected in this chapter.

Another fundamental phenomenon in equitable graph coloring is that in many graph classes “most” members admit equitable colorings with colors not extremely larger than their ordinary chromatic numbers. This phenomenon needs further investigated.

Equitable coloring of graphs can be formulated in terms of graph packings. This places equitable coloring in a wider context and gives it some previously unexpected connections and it may provide motivations to generate graph packing problems.

21 Cross-References

Advanced Techniques for Dynamic Programming

Advances in Scheduling Problems

Faster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches

On Coloring Problems

Online and Semi-online Scheduling

Resource Allocation Problems