J. Vernold Vivin^a , K. Kaliraj^b

^aDepartment of Mathematics, University College of Engineering Nagercoil, (Anna University Constituent College), Konam, Nagercoil- 629 004, Tamil Nadu, India.

vernoldvivin@yahoo.in, sk.kaliraj@gmail.com

The notion of equitable colorability was introduced by Meyer in 1973 [9]. In this paper we obtain interesting results regarding the equitable chromatic number χ⁼ for the corona graph of a simple graph with a wheel graph G ◦ Wn. Some extensions into l-corona products are also determined.

Keywords: equitable coloring, corona graph, wheel graph

Mathematics Subject Classification : 05C15

DOI:10.5614/ejgta.2016.4.2.8

1. Introduction

If the set of vertices of a graph G can be partitioned into k classes V1, V2, . . . , V^k such that each Vi is an independent set and the condition ||Vⁱ | − |V^j || ≤ 1 holds for every pair (i, j), then G is said to be equitably k-colorable. The smallest integer k for which G is equitably k-colorable is known as the equitable chromatic number [9] of G and denoted by χ=(G). This subject is widely discussed in literature [1, 4, 6, 7, 9]. In general, the problem of optimal equitable coloring, in the sense of number color used, is NP-hard.

The corona of two graphs G¹ and G² is the graph G = G¹ ◦ G² formed from one copy of G¹ and |V (G1)| copies of G² where the ith vertex of G¹ is adjacent to every vertex in the ith copy of G2. For any integer l ≥ 2, we define the graph G¹ ◦ ^l G² recursively from G¹ ◦ G² as

Received: 9 February 2015, Revised: 18 September 2016, Accepted: 29 September 2016.

^bDepartment of Mathematics, Ramanujan Institute for Advanced Study in Mathematics, University of Madras, Chepauk, Chennai-600 005, Tamil Nadu, India.

G¹ ◦ ^l G² = (G¹ ◦ ^l−¹ G2) ◦ G2. Graph G¹ ◦ ^l G² is also named as l-corona product of G¹ and G2. This kind of product was introduced by Harary and Frucht in 1970 [2].

Even more, we know [4] that the problem of the equitable coloring of corona graphs G ◦ H is NP-hard when G is 4-regular graph and H = K2. So we have to look for simplified structure of graphs allowing polynomial-time algorithms. This paper gives such solutions for corona graph of a simple graph with a wheel graph. Some extensions for l-corona products are also determined. This way we confirm Equitable Coloring Conjecture posed by Meyer [9] for graphs under consideration.

Conjecture 1 (Equitable Coloring Conjecture (ECC) [9]). For any connected graph G, other than the complete graph or odd cycle, χ=(G) ≤ ∆(G).

This conjecture has been verified for all graphs with six or fewer vertices. Lih and Wu [7] proved that the Equitable Coloring Conjecture (ECC) is true for all bipartite graphs. Wang and Zhang [10] considered a broader class of graphs, namely r-partite graphs. They proved that Meyer's conjecture is true for complete graphs from this class. The conjecture (or even the stronger one) was confirmed for outerplanar graphs [11] and planar graphs with maximum degree at least 13 [12].

Graph products are interesting and useful in many situations [5]. Equitable coloring of Cartesian, weak tensor and strong tensor products for some classes of graphs was considered in [3, 8].

For any integer n ≥ 4, the wheel graph Wⁿ is the n−vertex graph obtained by joining a vertex v¹ to each of the n − 1 vertices {w1, w2, . . . wn−1} of the cycle graph Cn−1.

2. Equitable coloring on corona graph of simple graph with wheel graph

We start with giving results for coronas of a single vertex and a wheel.

Theorem 2.1. Let n be a positive integer, n ≥ 4. Then

\[\chi_{=}(K_1 \circ W_n) = \left\lceil \frac{n-1}{2} \right\rceil + 2.\]

Proof. The color used for coloring the vertex of K¹ and the color used for coloring vertex v¹ cannot be used more times, so we can use any other color at most twice. Hence the value of the equitable chromatic number is equal to n − 1 2 + 2.

We notice that ∆(K¹ ◦ Wn) = n ≥ d(n − 1)/2e + 2 for n ≥ 4. This means that ECC holds for K¹ ◦ Wn, n ≥ 4.

Next, we consider coronas, where the set of vertices of graph G includes more than one element.

Theorem 2.2. Let G be an equitably 4-colorable graph on, m ≥ 2, vertices and let m be even, n be odd, and n ≥ 4, then

\[\chi_{=}(G \circ W_n) = 4.\]

Proof. Let ni(k) be the number of appearance of color k, 1 ≤ k ≤ 4, in the ith copy of Wⁿ corresponding to vertex uⁱ of G in G ◦ Wn, i = 1, 2, . . . , m.

Let f(ui) = j be the color assigned to vertex uⁱ (1 ≤ i ≤ m) of G. Since G is 4-colorable j takes the values in the range 1 ≤ j ≤ 4.

We color graph G equitably with four colors. We order the vertices of G: u1, u2, . . ., u^m in such a way that vertex uⁱ is colored with color i mod 4 - we use color 4 instead of color 0 (in some cases recoloring is needed). We extend this coloring into whole graph G◦ Wⁿ due to the following conditions. We consider two cases:

1. m mod 4 ≡ 0

If \[f(u_i) = j, u_i \in V(G), 1 \le j \le 4\], then

• ni((j + 1) mod 4) = 1,
• ⁿi((^j + 2) mod 4) = ^{n − 1} 2 and
• ⁿi((^j + 3) mod 4) = ^{n − 1} 2 .

In the above coloring, we use each color exactly (n+ 1)m/4 times. Graph G◦Wⁿ is colored equitably.

2. m mod 4 ≡ 2

We color first m − 2 copies of Wⁿ as we have colored the corresponding vertices in Case (1). We color last two copies in the following way. For each vertex uⁱ , i = m − 1, m, if f (ui) = j, 1 ≤ j ≤ 2, then the extended coloring must fulfill the following conditions.

• nⁱ ((j + 2)) = 1,
• ⁿⁱ ((^j + 3) mod 4) = ^{n − 1} 2 ,
• ⁿⁱ (^j + 1) = ^{n − 1} 2 .

We use each of four colors exactly (n+1)bm/4c+ (n+1)/2 times. Graph G◦Wⁿ is colored equitably.

Hence χ=(G ◦ Wn) ≤ 4. By the definition of corona graph, graph G ◦ Wⁿ contains K4. Hence χ=(G ◦ Wn) = 4.

Theorem 2.3. Let G be an equitably 4-colorable graph on 5 vertices, then

\[\chi_{=}(G \circ W_5) = 4.\]

Proof. Since W⁵ has the cycle C4, χ (W4) ≥ 3. By the definition of corona, each vertex uⁱ of G is adjacent to every vertex of its copy of Wn. Hence χ⁼ (G ◦ W5) ≥ 4.

By assigning the colors 1,2,3 and 4 as given below, it is concluded that the 1 appears 7 times, 2 appears 8 times, 3 appears 8 times and 4 appears 7 times. (i.e) The difference between the number of appearance of each pair of colors does not exceed one. Hence χ=(G ◦ W5) ≤ 4. Hence χ=(G ◦ W5) = 4.

Figure 1. An equitable 4-coloring of K1,1,1,² ◦ W⁵ with n(1) = n(4) = 7 and n(2) = n(3) = 8.

Now, we consider the remaining cases of m and n. It turns out that in these cases five colors are desirable for proper equitable coloring.

Theorem 2.4. Let G be an equitably 5-colorable graph on m vertices. If m mod 2 ≡ 1, n ≥ 7 or m, n even with n ≥ 4 then

\[\chi_{=}(G \circ W_n) = 5.\]

Proof. Let ni(k) be the number of appearance of color k, 1 ≤ k ≤ 5, in the ith copy of Wⁿ corresponding to vertex uⁱ of G in G ◦ Wn, i = 1, 2, . . . , m.

Let f(ui) = j be the color assigned to vertex uⁱ (1 ≤ i ≤ m) of G. Since G is 5-colorable j takes the values in the range 1 ≤ j ≤ 5.

We color graph G equitably with five colors. We order the vertices of G: u1, u2, . . ., u^m in such a way that vertex uⁱ is colored with color i mod 5 - we use color 5 instead of color 0 (in some cases recoloring is needed). We extend this coloring to the whole graph G ◦ Wⁿ due to the following conditions. We consider five cases dependently on the value of m.

1. m mod 5 ≡ 0

For each vertex uⁱ ∈ V (G) if f (ui) = j, 1 ≤ j ≤ 5, then

• ni((j + 1) mod 5) = 1,
• ni((j + 2) mod 5) = 1,
• ⁿi((^j + 3) mod 5) = n − 2 2 ,

• \[n_i((j+4) \bmod 5) = \left\lfloor \frac{n-2}{2} \right\rfloor\]

We use each of the five colors exactly (n+1)m/5 times. Graph \(G \circ W_n\) is colored equitably.

2. \(m \mod 5 \equiv 1\)

First, we color m-6 copies of \(W_n\) as we color the corresponding vertices in Case (1). We color last six copies in the following way. For each vertex \(u_i\) \((m-5 \le i \le m)\) we extend the coloring due to the following conditions, dependently on n.

(a) \(n \mod 5 \equiv 0\)

• For vertex \(u_{m-5}\) (\(f(u_{m-5}) = 1\)) we have \(n_{m-5}(2) = 1\), \(n_{m-5}(3) = n_{m-5}(4) = \frac{2n-5}{5}\), \(n_{m-5}(5) = \frac{n+5}{5}\).
• For vertex \(u_{m-4}\) (\(f(u_{m-4}) = 2\)) we have \(n_{m-4}(3) = 1\), \(n_{m-4}(1) = n_{m-4}(5) = \frac{2n-5}{5}\), \(n_{m-4}(4) = \frac{n+5}{5}\).
• For vertex \(u_{m-3}\) (\(f(u_{m-3}) = 3\)) we have \(n_{m-3}(4) = 1\), \(n_{m-3}(2) = \frac{2n}{5}\), \(n_{m-3}(5) = \frac{2n-10}{5}\), \(n_{m-3}(1) = \frac{n+5}{5}\).
• For vertex \(u_{m-2}\) (\(f(u_{m-2}) = 4\)) we have \(n_{m-2}(5) = 1\), \(n_{m-2}(3) = \frac{2n}{5}\), \(n_{m-2}(2) = \frac{2n-5}{5}\), \(n_{m-2}(1) = \frac{n}{5}\).
• For vertex \(u_{m-1}\) (\(f(u_{m-1}) = 5\)) we have \(n_{m-1}(3) = 1\), \(n_{m-1}(1) = n_{m-1}(2) = \frac{2n-5}{5}\), \(n_{m-1}(4) = \frac{n+5}{5}\).
• For vertex \(u_m\) (\(f(u_m) = 1\)) we have \(n_m(2) = 1\), \(n_m(3) = n_m(4) = \frac{2n-5}{5}\), \(n_m(5) = \frac{n+5}{5}\)

Each of the colors 1, 2, 3 and 5 are used (6n + 5)/5 times and color 4 is used (6n + 5)/5 + 1 times.

(b) \(n \mod 5 \equiv 1 \text{ or } n \mod 5 \equiv 4\)

• For vertex \(u_{m-5}\) (\(f(u_{m-5}) = 1\)) we have \(n_{m-5}(2) = 1\), \(n_{m-5}(3) = n_{m-5}(4) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_{m-5}(5) = \left\lceil \frac{n-1}{5} \right\rceil\).
• For vertex \(u_{m-4}\) (\(f(u_{m-4}) = 2\)) we have \(n_{m-4}(3) = 1\), \(n_{m-4}(1) = n_{m-4}(5) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_{m-4}(4) = \left\lceil \frac{n-1}{5} \right\rceil\).
• For vertex \(u_{m-3}\) (\(f(u_{m-3}) = 3\)) we have \(n_{m-3}(4) = 1\), \(n_{m-3}(2) = n_{m-3}(5) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_{m-3}(1) = \left\lceil \frac{n-1}{5} \right\rceil\).
• For vertex \(u_{m-2}\) (\(f(u_{m-2}) = 4\)) we have \(n_{m-2}(5) = 1\), \(n_{m-2}(2) = n_{m-2}(3) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_{m-2}(1) = \left\lceil \frac{n-1}{5} \right\rceil\).

• For vertex \(u_{m-1}\) (\(f(u_{m-1}) = 5\)) we have \(n_{m-1}(3) = 1\), \(n_{m-1}(1) = n_{m-1}(2) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_{m-1}(4) = \left\lceil \frac{n-1}{5} \right\rceil\).
• For vertex \(u_m\) (\(f(u_m) = 1\)) we have \(n_m(2) = 1\), \(n_m(3) = n_m(4) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_m(5) = \left\lceil \frac{n-1}{5} \right\rceil\).

Each of the colors 1, 4 and 5 are used \(2 + 2\lfloor 2n/5 \rfloor + 2\lceil (n-1)/5 \rceil\) times and colors 2 and 3 are used, each one with, \(3 + 3\lfloor 2n/5 \rfloor\) times. For \(n \mod 5 \equiv 1\) or \(n \mod 5 \equiv 4\), the difference does not exceed one.

• (c) \(n \mod 5 \equiv 2\)
  • For vertex \(u_{m-5}\) \((f(u_{m-5}) = 1)\) we have \(n_{m-5}(2) = 1\), \(n_{m-5}(3) = \frac{2n+1}{5}\), \(n_{m-5}(4) = \frac{2n-4}{5}\), \(n_{m-5}(5) = \frac{n-2}{5}\).
  • For vertex \(u_{m-4}\) (\(f(u_{m-4}) = 2\)) we have \(n_{m-4}(3) = 1\), \(n_{m-4}(1) = \frac{2n-4}{5}\), \(n_{m-4}(5) = \frac{2n+1}{5}\), \(n_{m-4}(4) = \frac{n-2}{5}\).
  • For vertex \(u_{m-3}\) (\(f(u_{m-3}) = 3\)) we have \(n_{m-3}(4) = 1\), \(n_{m-3}(2) = \frac{2n+1}{5}\), \(n_{m-3}(5) = \frac{2n-4}{5}\), \(n_{m-3}(1) = \frac{n-2}{5}\).
  • For vertex \(u_{m-2}\) (\(f(u_{m-2}) = 4\)) we have \(n_{m-2}(5) = 1\), \(n_{m-2}(2) = \frac{2n+1}{5}\), \(n_{m-2}(3) = \frac{2n-9}{5}\), \(n_{m-2}(1) = \frac{n+3}{5}\).
  • For vertex \(u_{m-1}\) (\(f(u_{m-1}) = 5\)) we have \(n_{m-1}(3) = 1\), \(n_{m-1}(1) = \frac{2n+1}{5}\), \(n_{m-1}(2) = \frac{2n-9}{5}\), \(n_{m-1}(4) = \frac{n+3}{5}\).
  • For vertex \(u_m\) \((f(u_m) = 1)\) we have \(n_m(2) = 1\), \(n_m(3) = \frac{2n+1}{5}\), \(n_m(4) = \frac{2n-4}{5}\), \(n_m(5) = \frac{n-2}{5}\).

Each of the colors 1, 2 and 3 are used (6n+3)/5+1 times and colors 4 and 5 are used, each one with, (6n+3)/5 times.

• (d) \(n \mod 5 \equiv 3\)
  • For vertex \(u_{m-5}\) (\(f(u_{m-5}) = 1\)) we have \(n_{m-5}(2) = 1\), \(n_{m-5}(3) = n_{m-5}(4) = \frac{2n-1}{5}\), \(n_{m-5}(5) = \frac{n-3}{5}\).
  • For vertex \(u_{m-4}\) (\(f(u_{m-4}) = 2\)) we have \(n_{m-4}(3) = 1\), \(n_{m-4}(1) = n_{m-4}(5) = \frac{2n-1}{5}\), \(n_{m-4}(4) = \frac{n-3}{5}\).

• For vertex \(u_{m-3}\) (\(f(u_{m-3}) = 3\)) we have \(n_{m-3}(4) = 1\), \(n_{m-3}(2) = n_{m-3}(5) = \frac{2n-1}{5}\), \(n_{m-3}(1) = \frac{n-3}{5}\).
• For vertex \(u_{m-2}\) (\(f(u_{m-2}) = 4\)) we have \(n_{m-2}(5) = 1\), \(n_{m-2}(2) = \frac{2n-1}{5}\), \(n_{m-2}(3) = \frac{2n-6}{5}\), \(n_{m-2}(1) = \frac{n+2}{5}\).
• For vertex \(u_{m-1}\) \((f(u_{m-1}) = 5)\) we have \(n_{m-1}(3) = 1\), \(n_{m-1}(1) = \frac{2n-1}{5}\), \(n_{m-1}(2) = \frac{2n-6}{5}\), \(n_{m-1}(4) = \frac{n+2}{5}\).
• For vertex \(u_m\) (\(f(u_m) = 1\)) we have \(n_m(2) = 1\), \(n_m(3) = n_m(4) = \frac{2n-1}{5}\), \(n_m(5) = \frac{n-3}{5}\).

Each of the colors 1, 2, 3 and 4 are used (6n + 2)/5 + 1 times and color 5 is used (6n + 2)/5 times.

In all the above cases the difference between the cardinalities of the color classes does not exceed one, so our coloring is equitable.

3. \(m \mod 5 \equiv 2\)

We color first m-2 copies of \(W_n\) as we color the corresponding vertices in Case (1). We color last two copies (for \(u_{m-1}\) and \(u_m\)) in the following way. We consider five cases dependently on n.

(a) \(n \mod 5 \equiv 0\)

• If \[f(u_i) = 1\], \(n_i(3) = 1\), \(n_i(2) = \frac{2n-5}{5}\), \(n_i(4) = \frac{2n-5}{5}\), \(n_i(5) = \frac{n+5}{5}\).

• If \[f(u_i) = 2\], \(n_i(4) = 1\), \(n_i(1) = n_i(3) = \frac{2n}{5}\), \(n_i(5) = \frac{n-5}{5}\).

(b) \(n \mod 5 \equiv 1 \text{ or } n \mod 5 \equiv 4\)

• If \[f(u_i) = 1\], \(n_i(3) = 1\), \(n_i(2) = n_i(4) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_i(5) = \left\lceil \frac{n-1}{5} \right\rceil\).

• If \[f(u_i) = 2\], \(n_i(4) = 1\), \(n_i(1) = n_i(3) = \left\lfloor \frac{2n}{5} \right\rfloor\), \(n_i(5) = \left\lceil \frac{n-1}{5} \right\rceil\).

(c) \(n \mod 5 \equiv 2\)

• If \[f(u_i) = 1\], \(n_i(3) = 1\), \(n_i(2) = n_i(4) = \frac{2n-4}{5}\), \(n_i(5) = \frac{n+3}{5}\).

• If \[f(u_i) = 2\], \(n_i(4) = 1\), \(n_i(1) = n_i(3) = \frac{2n-4}{5}\), \(n_i(5) = \frac{n+3}{5}\).

(d) \(n \mod 5 \equiv 3\)

• If \[f(u_i) = 1\], \(n_i(3) = 1\), \(n_i(2) = \frac{2n-6}{5}\), \(n_i(4) = \frac{2n-1}{5}\), \(n_i(5) = \frac{n+2}{5}\).

• If \[f(u_i) = 2\], \(n_i(4) = 1\), \(n_i(1) = n_i(3) = \frac{2n-1}{5}\), \(n_i(5) = \frac{n-3}{5}\).

In all the above cases the difference between the cardinalities of the color classes does not exceed one, so our coloring is equitable.

4. m mod 5 = 3

We color first m−8 copies of Wⁿ as we have colored the corresponding vertices in Case (1). For each vertex uⁱ (m − 7 ≤ i ≤ m) we extend the coloring due to following conditions, dependently on n.

• (a) n mod 5 ≡ 0 or n mod 5 ≡ 3
  • For vertex ^um−⁷ (^f (um−7) = 1) we have ⁿm−⁷ (2) = 1, ⁿm−⁷ (3) = 2n 5 , ⁿm−⁷ (4) = 2n 5 ^{− 1}, ⁿm−⁷ (5) = ^ln 5 m .
  • For vertex ^um−⁶ (^f (um−6) = 2) we have ⁿm−⁶ (1) = 1, ⁿm−⁶ (3) = 2n 5 − 1, ⁿm−⁶ (4) = 2n 5 , ⁿm−⁶ (5) = ^ln 5 m .
  • For vertex ^um−⁵ (^f (um−5) = 3) we have ⁿm−⁵ (4) = 1, ⁿm−⁵ (1) = 2n 5 , ⁿm−⁵ (2) = 2n 5 ^{− 1}, ⁿm−⁵ (5) = ^ln 5 m .
  • For vertex ^um−⁴ (^f (um−4) = 4) we have ⁿm−⁴ (3) = 1, ⁿm−⁴ (1) = 2n 5 − 1, ⁿm−⁴ (2) = 2n 5 , ⁿm−⁴ (5) = ^ln 5 m .
  • For vertex ^um−³ (^f (um−3) = 5 we have ⁿm−³ (1) = 1, ⁿm−³ (2) = 2n 5 , ⁿm−³ (3) = 2n 5 ^{− 1}, ⁿm−³ (4) = ^ln 5 m .
  • For vertex ^um−² (^f (um−2) = 1) we have ⁿm−² (2) = 1, ⁿm−² (3) = 2n 5 , ⁿm−² (5) = 2n 5 ^{− 1}, ⁿm−² (4) = ^ln 5 m .
  • For vertex ^um−¹ (^f (um−1) = 2) we have ⁿm−¹ (3) = 1, ⁿm−¹ (1) = 2n 5 − 1, ⁿm−¹ (5) = 2n 5 , ⁿm−¹ (4) = ^ln 5 m .
  • For vertex ^um (^f (um) = 3) we have ^nm (5) = 1, ^nm (1) = 2n 5 , n^m (2) = 2n 5 ^{− 1}, ^nm (4) = ^ln 5 m .

Each of the colors 1, 2 and 3 are used \(2 + 4\lfloor 2n/5 \rfloor\) times and colors 4 and 5 are used, each one with, \(2\lfloor 2n/5 \rfloor + 4\lceil n/5 \rceil + 1\) times. For \(n \mod 5 \equiv 0\) or \(n \mod 5 \equiv 3\), the difference does not exceed one.

• (b) \(n \mod 5 \equiv 1\)
  • For vertex \(u_{m-7}\) (\(f(u_{m-7}) = 1\)) we have \(n_{m-7}(2) = 1\), \(n_{m-7}(3) = n_{m-7}(4) = \frac{2n-2}{5}\), \(n_{m-7}(5) = \frac{n-1}{5}\).
  • For vertex \(u_{m-6}\) (\(f(u_{m-6}) = 2\)) we have \(n_{m-6}(1) = 1\), \(n_{m-6}(3) = \frac{2n-2}{5}\), \(n_{m-6}(4) = \frac{2n-7}{5}\), \(n_{m-6}(5) = \frac{n+4}{5}\).
  • For vertex \(u_{m-5}\) (\(f(u_{m-5}) = 3\)) we have \(n_{m-5}(4) = 1\), \(n_{m-5}(1) = n_{m-5}(2) = \frac{2n-2}{5}\), \(n_{m-5}(5) = \frac{n-1}{5}\).
  • For vertex \(u_{m-4}\) (\(f(u_{m-4}) = 4\)) we have \(n_{m-4}(3) = 1\), \(n_{m-4}(1) = \frac{2n-2}{5}\), \(n_{m-4}(2) = \frac{2n-7}{5}\), \(n_{m-4}(5) = \frac{n+4}{5}\).
  • For vertex \(u_{m-3}\) (\(f(u_{m-3}) = 5\)) we have \(n_{m-3}(1) = 1\), \(n_{m-3}(2) = n_{m-3}(3) = \frac{2n-2}{5}\), \(n_{m-3}(4) = \frac{n-1}{5}\).
  • For vertex \(u_{m-2}\) (\(f(u_{m-2}) = 1\)) we have \(n_{m-2}(2) = 1\), \(n_{m-2}(3) = \frac{2n-2}{5}\), \(n_{m-2}(5) = \frac{2n-7}{5}\), \(n_{m-2}(4) = \frac{n+4}{5}\).
  • For vertex \(u_{m-1}\) (\(f(u_{m-1}) = 2\)) we have \(n_{m-1}(3) = 1\), \(n_{m-1}(1) = n_{m-1}(5) = \frac{2n-2}{5}\), \(n_{m-1}(4) = \frac{n-1}{5}\).
  • For vertex \(u_m\) \((f(u_m) = 3)\) we have \(n_m(5) = 1\), \(n_m(1) = \frac{2n-7}{5}\), \(n_m(2) = \frac{2n-2}{5}\), \(n_m(4) = \frac{n+4}{5}\).

Each of the colors 1, 2, 4 and 5 are used (8n + 7)/5 times and color 3 is used (8n + 7)/5 + 1 times.

• (c) \(n \mod 5 \equiv 2\)
  • For vertex \(u_{m-7}\) (\(f(u_{m-7}) = 1\)) we have \(n_{m-7}(2) = 1\), \(n_{m-7}(3) = \frac{2n+1}{5}\), \(n_{m-7}(4) = \frac{2n-4}{5}\), \(n_{m-7}(5) = \frac{n-2}{5}\).
  • For vertex \(u_{m-6}\) (\(f(u_{m-6}) = 2\)) we have \(n_{m-6}(1) = 1\), \(n_{m-6}(3) = n_{m-6}(4) = \frac{2n-4}{5}\), \(n_{m-6}(5) = \frac{n+3}{5}\).
  • For vertex \(u_{m-5}\) \((f(u_{m-5}) = 3)\) we have \(n_{m-5}(4) = 1\), \(n_{m-5}(1) = \frac{2n+1}{5}\), \(n_{m-5}(2) = \frac{2n-4}{5}\), \(n_{m-5}(5) = \frac{n-2}{5}\).

• For vertex \(u_{m-4}\) (\(f(u_{m-4}) = 4\)) we have \(n_{m-4}(3) = 1\), \(n_{m-4}(1) = n_{m-4}(2) = \frac{2n-4}{5}\), \(n_{m-4}(5) = \frac{n+3}{5}\).
• For vertex \(u_{m-3}\) \((f(u_{m-3}) = 5)\) we have \(n_{m-3}(1) = 1\), \(n_{m-3}(2) = \frac{2n+1}{5}\), \(n_{m-3}(3) = \frac{2n-4}{5}\), \(n_{m-3}(4) = \frac{n-2}{5}\).
• For vertex \(u_{m-2}\) (\(f(u_{m-2}) = 1\)) we have \(n_{m-2}(2) = 1\), \(n_{m-2}(3) = n_{m-2}(5) = \frac{2n-4}{5}\), \(n_{m-2}(4) = \frac{n+3}{5}\).
• For vertex \(u_{m-1}\) \((f(u_{m-1}) = 2)\) we have \(n_{m-1}(3) = 1\), \(n_{m-1}(1) = \frac{2n-4}{5}\), \(n_{m-1}(5) = \frac{2n+1}{5}\), \(n_{m-1}(4) = \frac{n-2}{5}\).
• For vertex \(u_m\) (\(f(u_m) = 3\)) we have \(n_m(5) = 1\), \(n_m(1) = n_m(2) = \frac{2n-4}{5}\), \(n_m(4) = \frac{n+3}{5}\).

Each of the colors 1, 2, 3 and 5 are used (8n + 4)/5 + 1 times and color 4 is used (8n + 4)/5 times.

• (d) \(n \mod 5 \equiv 4\)
  • For vertex \(u_{m-7}\) (\(f(u_{m-7}) = 1\)) we have \(n_{m-7}(2) = 1\), \(n_{m-7}(3) = n_{m-7}(4) = \frac{2n-3}{5}\), \(n_{m-7}(5) = \frac{n+1}{5}\).
  • For vertex \(u_{m-6}\) (\(f(u_{m-6}) = 2\)) we have \(n_{m-6}(1) = 1\), \(n_{m-6}(3) = n_{m-6}(4) = \frac{2n-3}{5}\), \(n_{m-6}(5) = \frac{n+1}{5}\).
  • For vertex \(u_{m-5}\) (\(f(u_{m-5}) = 3\)) we have \(n_{m-5}(4) = 1\), \(n_{m-5}(1) = n_{m-5}(2) = \frac{2n-3}{5}\), \(n_{m-5}(5) = \frac{n+1}{5}\).
  • For vertex \(u_{m-4}\) (\(f(u_{m-4}) = 4\)) we have \(n_{m-4}(3) = 1\), \(n_{m-4}(1) = n_{m-4}(2) = \frac{2n-3}{5}\), \(n_{m-4}(5) = \frac{n+1}{5}\).
  • For vertex \(u_{m-3}\) (\(f(u_{m-3}) = 5\)) we have \(n_{m-3}(1) = 1\), \(n_{m-3}(2) = n_{m-3}(3) = \frac{2n-3}{5}\), \(n_i(4) = \frac{n+1}{5}\).
  • For vertex \(u_{m-2}\) (\(f(u_{m-2}) = 1\)) we have \(n_{m-2}(2) = 1\), \(n_{m-2}(3) = n_{m-2}(5) = \frac{2n-3}{5}\), \(n_{m-2}(4) = \frac{n+1}{5}\).
  • For vertex \(u_{m-1}\) (\(f(u_{m-1}) = 2\)) we have \(n_{m-1}(3) = 1\), \(n_{m-1}(1) = n_{m-1}(5) = \frac{2n-3}{5}\), \(n_{m-1}(4) = \frac{n+1}{5}\).
  • For vertex \(u_m\) (\(f(u_m) = 3\)) we have \(n_m(5) = 1\), \(n_m(1) = n_m(2) = \frac{2n-3}{5}\), \(n_m(4) = \frac{n+1}{5}\).

Each of the colors are used (8n + 8)/5 times.

In all the above cases the difference between the cardinalities of the color classes does not exceed one, so our coloring is equitable.

5. \(m \mod 5 \equiv 4\)

We color first m-4 copies of \(W_n\) as we have colored the corresponding vertices in Case (1). Then, we color last four copies in the following way. For each vertex \(u_i\), \((m-3 \le i \le m)\), we color the corresponding copy of \(W_n\) due the following conditions, dependently on n.

(a) \(n \mod 5 \equiv 0\)

If \(f(u_i) = j\), \(1 \le j \le 4\), then

• \[n_i((j+1) \mod 4) = 1\],

• \[n_i((j+2) \mod 4) = \frac{2n}{5}\],

• \[n_i((j+3) \mod 4) = \frac{2n-5}{5}\],

\[\bullet \ n_i(5) = \frac{n}{5}.\]

(b) \(n \mod 5 \equiv 1\)

For vertex \(u_{m-3}\) (\(f(u_{m-3}) = 1\)) we have \(n_{m-3}(2) = 1\), \(n_{m-3}(3) = \frac{2n-2}{5}\),

\[n_{m-3}(4) = \frac{2n-7}{5}, n_{m-3}(5) = \frac{n+4}{5}.\]

For vertices \(u_i\), \(m-2 \le i \le m\), if \(f(u_i) = j\), \(1 \le j \le 4\), then

• \[n_i((j+1) \mod 4) = 1\],

• \[n_i((j+2) \mod 4) = n_i((j+3) \mod 4) = \frac{2n-2}{5}\],

\[\bullet \ n_i(5) = \frac{n-1}{5}.\]

(c) \(n \mod 5 \equiv 2\)

For vertices \(u_i\), \(m-3 \le i \le m-2\), if \(f(u_i)=j\), \(1 \le j \le 2\), then

• \[n_i((j+1) \mod 4) = 1\],

• \[n_i((j+2) \mod 4) = n_i((j+3) \mod 4) = \frac{2n-4}{5}\],

\[\bullet \ n_i(5) = \frac{n+3}{5}.\]

For vertices \(u_i\), \(m-1 \le i \le m\), if \(f(u_i) = j\), \(3 \le j \le 4\), then

• \[n_i((j+1) \mod 4) = 1\],

• \[n_i((j+2) \mod 4) = \frac{2n+1}{5}\],

• \[n_i((j+3) \mod 4) = \frac{2n-4}{5}\],

• \[n_i(5) = \frac{n-2}{5}\].

(d) \(n \mod 5 \equiv 3\)

If \(f(u_i) = j\), \(1 \le j \le 4\), then

• \[n_i((j+1) \mod 4) = 1\],

• \[n_i((j+2) \mod 4) = \frac{2n-1}{5}\],

• \[n_i((j+3) \mod 4) = \frac{2n-6}{5}\],

• \[n_i(5) = \frac{n+2}{5}\].

(e) \(n \mod 5 \equiv 4\)

If \(f(u_i) = j\), \(1 \le j \le 4\), then

• \[n_i((j+1) \mod 4) = 1\],

• \[n_i((j+2) \mod 4) = n_i((j+3) \mod 4) = \frac{2n-3}{5}\],

• \[n_i(5) = \frac{n+1}{5}\].

In all the above cases the difference between the cardinalities of the color classes does not exceed one, so our coloring is equitable. Hence \(\chi_{=}(G \circ W_n) \leq 5\). By the definition of corona graph for each vertex \(u_i\) of G, there exists a copy of \(W_n\) whose vertices are adjacent to the vertex \(u_i\).

Case 1: If \(m \mod 2 \equiv 1, n \geq 7\)

In this case either both m and n are odd (or) m is odd and n is even.

(a) If m and n are odd.

Since \(\chi(W_n)=3\) for odd n, we need at least 4 colors for coloring each copy of \(W_n\) and the corresponding vertex of G. In this coloring, since m is odd there exists at least one color which reappears in \(\langle \{u_i: 1 \leq i \leq m\} \rangle\). Let the color j \((1 \leq j \leq 4)\) reappears at the vertex \(u_i\) \((5 \leq i \leq m)\). Then the center vertex of the copy \(W_n\) corresponding to the vertex \(u_i\), receives a color k \((1 \leq k \leq 4)\), where \(k \neq j\). Other vertices of \(W_n\) receive the colors other than j and k. (i.e) The number of possible colors to color these vertices is two. Hence it is clear that for the case of \(n \geq 5\), it is not possible to color the vertices of the cycle \(C_{n-1}\) of \(W_n\) equitably with two colors. Therefore \(\chi_=(G \circ W_n) \geq 5\). Hence \(\chi_=(G \circ W_n) = 5\) for m and n are odd.

(b) If m is odd and n is even.

Since \(\chi(W_n) = 4\) for even n, the graph \(G \circ W_n\) requires at least 5 colors. Hence \(\chi_{=}(G \circ W_n) = 5\) for m is odd and n is even.

Case 2: If m and n are even, \(n \ge 4\)

Since \(\chi(W_n)=4\) for even n, graph \(G\circ W_n\) requires at least 5 colors. Therefore \(\chi_{=}(G\circ W_n)\geq 5\).

Hence \(\chi_{=}(G \circ W_n) = 5\) for even n.

Next, we consider coronas, where the set of vertices of graph G includes exactly three elements.

Theorem 2.5. Let G be an equitably 3-colorable graph with m = 3 vertices. Then

• 1. χ=(G W5) = 4.
• 2. χ=(G Wn) = 5 n = 7, 9, 11, 13, 15, 17.
• 3. χ=(G Wn) = 5 n ≥ 19, if n is odd.
• 4. χ=(G Wn) = 5 n = 4, 6, 8, 10.
• 5. χ=(G Wn) = 6 n ≥ 12, if n is even.

Proof. Let {uⁱ : 1 ≤ i ≤ 3} be the set of vertices of G.

• 1. We color G W⁵ as for the following procedure.
  • For vertex u¹ (f(u1) = 1) we have n¹ (2) = 1, n¹ (3) = n¹ (4) = 2.
  • For vertex u² (f(u2) = 2) we have n² (3) = 1, n² (4) = n² (1) = 2.
  • For vertex u³ (f(u3) = 3) we have n³ (4) = 1, n³ (1) = n³ (2) = 2.

In the above cases the difference between the cardinalities of the color classes does not exceed one, so our coloring is equitable. Hence χ=(G ◦ W5) ≤ 4. Since W⁵ is 3-colorable, at each copy of W⁵ of G ◦ W5, there exists one more color. Therefore χ=(G ◦ W5) ≥ 4. hence χ=(G ◦ W5) = 4.

• 2. Assign the color i to the vertex uⁱ (1 ≤ i ≤ 3), color 4 to the vertex u1n, color 5 to the vertex u2ⁿ and color 1 to the vertex u3n. Since Cn−¹ is of even order, we require only two colors for proper coloring of Cn−1. We use three colors in each Cn−¹ of Wⁿ in G ◦ Wn. We use the colors 2,3,5 to the vertices of Cn−¹ of Wⁿ at u1. Similarly we use the colors 1,3,4 and 4,5,2 to the vertices of Cn−¹ of Wⁿ at u² and u³ respectively. The number of appearance of the colors are given in the following cases.
  • (a) n = 7, 17
    • For vertex ^u1 (^f (u¹ = 1)) we have ⁿ¹ (4) = 1, ⁿ¹ (2) = ²ⁿ + 1 5 , n¹ (3) = 2n − 4 5 , ⁿ¹ (5) = ^{n − 2} 5 .
    • For vertex ^u2 (^f (u² = 2)) we have ⁿ² (5) = 1, ⁿ² (1) = ^{n − 1} 2 , ⁿ² (3) = n − 1 4 , ⁿ² (4) = n − 1 4 .
    • For vertex ^u3 (^f (u³ = 3)) we have ⁿ³ (1) = 1, ⁿ³ (4) = ^{2n − 4} 5 , n³ (5) = 2n + 1 5 , ⁿ³ (2) = ^{n − 2} 5 .
  • (b) n = 9
    • For vertex u¹ (f (u1) = 1) we have n¹ (4) = 1, n¹ (2) = n¹ (3) = 3, n¹ (5) = 2.
    • For vertex u² (f (u2) = 2) we have n² (5) = 1, n² (1) = 4, n² (3) = n² (4) = 2.

• For vertex \(u_3\) (\(f(u_3) = 3\)) we have \(n_3(1) = 1\), \(n_3(4) = n_3(5) = 3\), \(n_3(2) = 2\).
• (c) n = 11
  • For vertex \(u_1(f(u_1) = 1)\) we have \(n_1(4) = 1\), \(n_1(2) = n_1(3) = 4\), \(n_1(5) = 2\).
  • For vertex \(u_2(f(u_2) = 2)\) we have \(n_2(5) = 1\), \(n_2(1) = 5\), \(n_2(3) = 3\), \(n_2(4) = 2\).
  • For vertex \(u_3\) (\(f(u_3) = 3\)) we have \(n_3(1) = 1\), \(n_3(4) = n_3(5) = 4\), \(n_3(2) = 2\).
• (d) n = 13
  • For vertex \(u_1(f(u_1) = 1)\) we have \(n_1(4) = 1\), \(n_1(2) = n_1(3) = 5\), \(n_1(5) = 2\).
  • For vertex \(u_2(f(u_2) = 2)\) we have \(n_2(5) = 1\), \(n_2(1) = 6\), \(n_2(3) = 3\), \(n_2(4) = 3\).
  • For vertex \(u_3\) (\(f(u_3) = 3\)) we have \(n_3\) (1) = 1, \(n_3\) (4) = \(n_3\) (5) = 5, \(n_3\) (2) = 2.
• (e) n = 15
  • For vertex \(u_1(f(u_1) = 1)\) we have \(n_1(4) = 1\), \(n_1(2) = n_1(3) = 6\), \(n_1(5) = 2\).
  • For vertex \(u_2(f(u_2) = 2)\) we have \(n_2(5) = 1\), \(n_2(1) = 7\), \(n_2(3) = 3\), \(n_2(4) = 4\).
  • For vertex \(u_3\) (\(f(u_3) = 3\)) we have \(n_3\) (1) = 1, \(n_3\) (4) = 4, \(n_3\) (5) = 7, \(n_3\) (2) = 2.

In the above cases the difference between the cardinalities of the color classes does not exceed one, so our coloring is equitable. Hence \(\chi_{=}(G \circ W_n) \leq 5\).

Since G is 3-colorable, let i be the color assigned to the vertex \(u_i\) \((1 \le i \le 3)\) of \(G \circ W_n\). Let j \((1 \le j \le 4)\), \((i \ne j)\) be the color assigned to the center vertices of each copy \(W_n\) of \(G \circ W_n\). The other vertices of these copies receive the colors other than i and j. (i.e) The number of possible colors to color these vertices is two. Hence it is clear that for the case of n = 7, 9, 11, 13, 15, 17, it is not possible to color the vertices of the cycle \(C_{n-1}\) of \(W_n\) equitably with two colors. Therefore \(\chi_{=}(G \circ W_n) \ge 5\). Hence \(\chi_{=}(G \circ W_n) = 5\) for n = 7, 9, 11, 13, 15, 17.

3. Suppose that \(G \circ W_n\) is 4-equitably colorable. Since G is 3-colorable, let it be colored by the color 1,2 and 3. Let \(u_i\) receives the color \(i (1 \le i \le 3)\). Then \(u_{1n}, u_{2n}\) and \(u_{3n}\) should receive any two of the three color 1,2,3 and the color 4.

Let \(u_{1n}\) receive 4, \(u_{2n}\) receive 1 and \(u_{2n}\) receive 2. Then \(u_{1i}\) \((1 \le i \le n-1)\) receives the color 2, \(\frac{n-1}{2}\) times and 3, \(\frac{n-1}{2}\) times. \(u_{2i}\) \((1 \le i \le n-1)\) receives the color 3, \(\frac{n-1}{2}\)

times, the color 4, \(\frac{n-1}{2}\) times. Similarly \(u_{3i}\) receives the color 1, \(\frac{n-1}{2}\) times and the color 1, \(\frac{n-1}{2}\) times.

Number of appearance of each colors 1 and 2 are, \(\frac{n+3}{2}\) times respectively and number of appearance of each colors 3 and 4 are, n times respectively.

As the above mentioned partition does not imply the equitable partition, it is concluded that \(G \circ W_n\) should not be equitable 4-colorable.

Hence \[\chi_{=}(G \circ W_n) \geq 5\]

Suppose that \(G \circ W_n\) is 5-equitable colorable. Let G be colored by the colors 1, 2 and 3. Let \(u_i\) receives the color i (\(1 \le i \le 3\)). Since \(G \circ W_n\) is 5-equitable colorable, any two of the vertices \(u_{1n}, u_{2n}\) and \(u_{3n}\) receives the color 4 and 5 (Say \(u_{1n}, u_{2n}\)) and remaining vertex \(u_{3n}\) should receive the color 1.

For the case of \(n \ge 19\), if we use the above coloring with 5 colors, then the maximum of appearance of color \(1, \frac{n-1}{2} + 2 = \frac{n+3}{2}\) times.

Remaining number of vertices to be colored are, \(3n + 3 - \frac{n+3}{2} = \frac{5n+3}{2}\).

Number of vertices which receive each colors of 2, 3, 4 and 5 are \(\frac{5n+3}{4} = \frac{5n+3}{8}\).

For \[n \ge 19\], \(\left\lceil \frac{5n+3}{2} \right\rceil - \left\lceil \frac{n+3}{2} \right\rceil \ge 2\).

(i.e) it may not be possible to equitably color \(G \circ W_n\) with 5 colors. \(\chi = (G \circ W_n) \ge 6\).

• For vertex \(u_1(f(u_1) = 1)\) we have \(n_1(4) = 1\), \(n_1(2) = n_1(3) = \frac{n-1}{2}\).
• For vertex \(u_2(f(u_2) = 2)\) we have \(n_2(5) = 1\), \(n_2(1) = n_2(6) = \frac{n-1}{2}\).
• For vertex \(u_3\) (\(f(u_3) = 3\)) we have \(n_3\) (6) = 1, \(n_3\) (5) = \(n_3\) (4) = \(\frac{n-1}{2}\).

In the above cases the difference between the cardinalities of color classes does not exceed one, so our coloring is equitable. Hence \(\chi = (G \circ W_n) = 6\), \(n \ge 19\), if n is odd.

4. Since n is even \(W_n\) has odd cycle \(C_{n-1}\). Minimum number of colors assigned to color any cycle is 3. Hence \(u_{in}\) \((1 \le i \le n)\) should have a fourth color and hence \(u_i\) \((1 \le i \le n)\) must receive a fifth color. Hence \(\chi_{=}(G \circ W_n) \ge 5\).

Now we partition the vertex set \(V(G \circ W_n)\) as follows,

\[V_1 = \{u_1, u_{21}, u_{23}, u_{25}, u_{28}, u_{3n}\}\] \[V_2 = \{u_2, u_{11}, u_{14}, u_{18}, u_{33}, u_{36}, u_{39}\}\] \[V_3 = \{u_3, u_{12}, u_{15}, u_{17}, u_{24}, u_{27}\}\] \[V_4 = \{u_{1n}, u_{22}, u_{26}, u_{29}, u_{32}, u_{35}, u_{37}\}\] \[V_5 = \{u_{2n}, u_{13}, u_{16}, u_{19}, u_{31}, u_{34}, u_{38}\}\]

Clearly \(V_1, V_2, V_3, V_4\) and \(V_5\) are independent set of \(G \circ W_n\). Hence \(||V_i| - |V_j|| \le 1\) for every \(i \ne j\). Hence \(\chi = (G \circ W_n) = 5\), \(4 \le n \le 10\), if n is even.

5. Let \(n_i(k)\) be the number of appearance of the color k in the copy of \(W_n\) corresponding to the vertex \(u_i\) of G in \(G \circ W_n\).

Let \(f(u_i) = j\) be the color assigned to each vertices \(u_i (1 \le i \le m)\) of G. Since G is 6-colorable j takes the values in the range \(1 \le j \le 6\).

• For vertex \(u_1(f(u_1) = 1)\) we have \(n_1(2) = n_1(5) = 1\), \(n_1(3) = n_1(4) = \frac{n-2}{2}\).
• For vertex \(u_2(f(u_2) = 2)\) we have \(n_2(3) = n_2(1) = 1\), \(n_2(5) = n_2(6) = \frac{n-2}{2}\).
• For vertex \(u_3\) (\(f(u_3) = 3\)) we have \(n_3\) (6) = \(n_3\) (4) = 1, \(n_3\) (1) = \(n_3\) (2) = \(\frac{n-2}{2}\).

In the above cases the difference between the cardinalities of the color classes does not exceed one, so our coloring is equitable. Hence \(\chi_{=}(G \circ W_n) \leq 6\)

Since n is even, we require at least 3 colors to color each \(C_{n-1}\) of \(W_n\), one color for the centre vertex of \(W_n\) and one color corresponding to the vertex of G. Hence we may assume that \(\chi_{=}(G\circ W_n)=5\). It is clear that one of these five colors appears twice in \(\langle \{u_i:1\leq i\leq 3\}\bigcup\{u_{in}:1\leq i\leq 3\}\rangle\), let it be color j \((1\leq j\leq 5)\). This color j can be assigned only \(\frac{n-2}{2}\) times in any of the \(C_{n-1}\) copy of \(W_{n-1}\). This violate the equitable conclusion.

Therefore \[\chi_{=}(G \circ W_n) \geq 6\]. Hence \(\chi_{=}(G \circ W_n) = 6\).

3. Conclusion

We notice that the results can be extended into further products of graphs.

Corollary 3.1. Let G be an equitably 4-colorable graph on, \(m \ge 2\), vertices, let m is even, n is odd, and \(n \ge 4\), and \(l \ge 1\). Then

\[\chi_{=}^{l}(G \circ W_n) = 4.\]

Proof. We use the principle of mathematical induction due to number l.

• 1. l=1 The truth follows immediately from Theorem 2.2.
• 2. Induction hypothesis for l. It means that \(\chi_{=}(G \circ^{l} W_{n}) = 4\) for n odd and m = |V(G)| even.
• 3. We must show that \(\chi_{=}(G \circ^{l+1} W_n) = 4\) for graphs under consideration.

Let us notice that graph from induction hypothesis \(G \circ^l W_n\) is an equitably 4-colorable graph, it means a graph fulfilling the assumption of Theorem 2.2. Its number of vertices, equals to \(m(n+1)^l\) is an even number for m even. So, \(\chi_=(G \circ^{l+1} W_n) = 4\).

Corollary 3.2. Let G be an equitably 5-colorable graph on m vertices and let \(m \ge 2\), \(n \ge 4\), \(l \ge 1\). Then

\[\chi_{=}(G \circ^{l} W_{n}) = \begin{cases} = 5 & \text{for } n \text{ even,} \\ \leq 5 & \text{for } m \text{ and } n \text{ odd.} \end{cases}\]

Proof. Follows immediately from Theorem 2.4.

Acknowledgement

With due Respect, the authors sincerely thank the referee for his careful reading, excellent comments and fruitful suggestions that have resulted in the improvement of the quality of this manuscript.

References

• [1] B. L. Chen and K. W. Lih, Equitable coloring of trees, J. Combin. Theory Ser. B 61 (1994), 83–87.
• [2] R. Frucht and F. Harary, On the corona of two graphs, Aequationes Math. 4 (1970), 322-325.
• [3] H. Furmanczyk, Equitable coloring of graph products, ´ Opuscula Mathematica 26 (2006), 31–44.
• [4] H. Furmanczyk, K. Kaliraj, M. Kubale, and J. Vernold Vivin, Equitable coloring of corona ´ product of graphs, Advances and Applications of Discrete Mathematics 11(2) (2013), 103– 120.
• [5] S. Klavzar, R. Hammack, and W. Imrich, Handbook of graph products, CRC Press (2011).
• [6] M. Kubale, Graph Colorings, American Mathematical Society Providence, Rhode Island- (2004).
• [7] K. W. Lih and P. L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151 (1996), 155–160.
• [8] W. H. Lin and G. J. Chang, Equitable colorings of Cartesian products of graphs, Disc. App. Math. 160 (2012), 239–247.
• [9] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973), 920–922.
• [10] W. Wang and K. Zhang, Equitable colorings of line graphs and complete r-partite graphs, Systems Science and Mathematical Sciences 13 (2000), 190–194.
• [11] H. P. Yap and Y. Zhang, The Equitable ∆-Coloring Conjecture holds for outerplanar graphs, Bulletin of the Inst. of Math. Academia Sinica 25 (1997), 143–149.
• [12] H. P. Yap and Y. Zhang, Equitable colourings of planar graphs, J. Comb. Math. Comb. Comput. 27 (1998), 97–105.