Article Search
eISSN 0454-8124
pISSN 1225-6951

### Article

KYUNGPOOK Math. J. 2019; 59(4): 591-601

Published online December 23, 2019

### The Zero-divisor Graph of the Ring of Integers Modulo n

Seung Jun Pi, Se Hun Kim, Jung Wook Lim∗

Department of Mathematics, College of Natural Sciences, Kyungpook National University, Daegu, 41566, Republic of Korea
e-mail : seungjunpi0@gmail.com
Department of Mathematics, Seoul National University, Seoul, 03080, Republic of Korea
e-mail : shunhun33@gmail.com
Department of Mathematics, College of Natural Sciences, Kyungpook National University, Daegu, 41566, Republic of Korea
e-mail : jwlim@knu.ac.kr

Received: October 15, 2018; Revised: September 5, 2019; Accepted: November 11, 2019

Let ℤn be the ring of integers modulo n and Γ(ℤn) the zero-divisor graph of ℤn. In this paper, we study some properties of Γ(ℤn). More precisely, we completely characterize the diameter and the girth of Γ(ℤn). We also calculate the chromatic number of Γ(ℤn).

Keywords: zero-divisor graph, ring of integers modulo n, diameter, girth, clique, chromatic number.

### 1.1. Preliminaries

In this subsection, we review some concepts from basic graph theory. Let G be a (undirected) graph. Recall that G is connected if there is a path between any two distinct vertices of G. The graph G is complete if any two distinct vertices are adjacent. The complete graph with n vertices is denoted by Kn. The graph G is a complete bipartite graph if G can be partitioned into two disjoint nonempty vertex sets A and B such that two distinct vertices are adjacent if and only if they are in distinct vertex sets. If one of the vertex sets is a singleton set, then we call G a star. We denote the complete bipartite graph by Km,n, where m and n are the cardinal numbers of A and B, respectively. For vertices a and b in G, d(a, b) denotes the length of the shortest path from a to b. If there is no such path, then d(a, b) is defined to be ∞; and d(a, a) is defined to be zero. The diameter of G, denoted by diam(G), is the supremum of {d(a, b) | a and b are vertices of G}. The girth of G, denoted by g(G), is defined as the length of the shortest cycle in G. If G contains no cycles, then g(G) is defined to be ∞. A subgraph H of G is an induced subgraph of G if two vertices of H are adjacent in H if and only if they are adjacent in G. The chromatic number of G is the minimum number of colors needed to color the vertices of G so that no two adjacent vertices share the same color, and is denoted by χ(G). A clique C in G is a subset of the vertex set of G such that the induced subgraph of G by C is a complete graph. The clique number of G, denoted by cl(G), is the greatest integer n ≥ 1 such that KnG. If KnG for all integers n ≥ 1, then cl(G) is defined to be ∞. A maximal clique in G is a clique that cannot be extended by including one more adjacent vertex. It is easy to see that χ(G) ≥ cl(G).

### 1.2. The Zero-divisor Graph of a Commutative Ring

Let R be a commutative ring with identity and Z(R) the set of nonzero zero-divisors of R. The zero-divisor graph of R, denoted by Γ(R), is the simple graph with vertex set Z(R), and for distinct a, b ∈ Z(R), a and b are adjacent if and only if ab = 0. Clearly, Γ(R) is the null graph if and only if R is an integral domain.

In [4], Beck first introduced the concept of the zero-divisor graphs of commutative rings and in [3], Anderson and Nazeer continued the study. In their papers, all elements of R are vertices of the graph and they were mainly interested in colorings. In [2], Anderson and Livingston gave the present definition of Γ(R) in order to emphasize the study of the interplay between graph-theoretic properties of Γ(R) and ring-theoretic properties of R. It was shown that Γ(R) is connected with diam(Γ(R)) ≤ 3 [2, Theorem 2.3]; and g(Γ(R)) ≤ 4 [5, (1.4)].

For more on the zero-divisor graph of a commutative ring, the readers can refer to a survey article [1].

Let ℤn be the ring of integers modulo n. The purpose of this paper is to study some properties of the zero-divisor graph of ℤn. If n is a prime number, then ℤn has no zero-divisors; so Γ(ℤn) is the null graph. Hence in this paper, we only consider the case that n is a composite. In Section 2, we completely characterize the diameter and the girth of Γ(ℤn). In Section 3, we calculate the chromatic number of Γ(ℤn). Note that all figures are drawn via website http://graphonline.ru/en/.

### 2. The Diameter and the Girth of Γ(ℤn)

Our first result in this section is the complete characterization of the diameter of Γ(ℤn).

### Theorem 2.1

The following statements hold.

(1) diam(Γ(ℤn)) = 0 if and only if n = 4.

(2)diam(Γ(ℤn)) = 1 if and only if n = p2for some prime p ≥ 3.

(3)diam(Γ(ℤn)) = 2 if and only if n = pr for some prime p and some integer r ≥ 3, or n = pq for some distinct primes p and q.

(4)diam(Γ(ℤn)) = 3 if and only if n = pqr for some distinct primes p, q and some integer r ≥ 2.

Proof

(1) If n = 4, then Z(ℤ4) = {2}; so diam(Γ(ℤ4)) = 0.

(2) If n = p2 for some prime p ≥ 3, then Z(ℤp2) = {p, 2p, …, (p − 1)p}; so the product of any two elements of Z(ℤp2) is zero. Hence Γ(ℤp2) is the complete graph Kp−1. Thus diam(Γ(ℤp2)) = 1.

(3) If n = pr for some prime p and some integer r ≥ 3, then Z(ℤpr) = {p, 2p, …, (pr−1 − 1)p}; so apr−1 = 0 for all a ∈ Z(ℤpr). Hence diam(Γ(ℤpr)) ≤ 2. Note that p((pr−1 − 1)p) ≠ = 0. Thus diam(Γ(ℤpr)) = 2.

If n = pq for some distinct primes p and q, then Z(ℤpq) = {p, 2p, …, (q − 1)p, q, 2q, …, (p − 1)q}; so (ip)(jq) = 0 for all i = 1, …, q − 1 and j = 1, …, p − 1. Note that for any a, b ∈ {p, 2p, …, (q − 1)p} and c, d ∈ {q, 2q, …, (p − 1)q}, ab ≠ = 0 and cd ≠ = 0. Hence Γ(ℤpq) is the complete bipartite graph Kp−1,q−1. Thus diam(Γ(ℤpq)) = 2.

(4) Suppose that n = pqr for some distinct primes p, q and some integer r ≥ 2. Then p, q ∈ Z(ℤpqr) with pq ≠ = 0; so diam(Γ(ℤpqr)) ≥ 2. If there exists an element a ∈ Z(ℤpqr) such that p ~ a ~ q is a path, then a is a nonzero multiple of pr and qr; so a is nonzero a multiple of pqr. This is a contradiction. Hence diam(Γ(ℤpqr)) ≥ 3. Thus diam(Γ(ℤpqr)) = 3 [2, Theorem 2.3].

We next study the girth of Γ(ℤn).

### Lemma 2.2

If g(Γ(ℤn)) = 3, then g(Γ(ℤmn)) = 3 for all integers m ≥ 1.

Proof. Note that if a ~ b ~ c ~ a is a cycle in Γ(ℤn), then am ~ bm ~ cm ~ am is a cycle in Γ(ℤmn). Thus g(Γ(ℤmn)) = 3.

The next example shows that Lemma 2.2 cannot be extended to the case of girth 4.

### Example 2.3

(1) Note that g(Γ(ℤ12)) = 4. In fact, 3 ~ 4 ~ 6 ~ 8 ~ 3 is a cycle of length 4 in Γ(ℤ12). However, g(Γ(ℤ24)) = 3 because 6 ~ 8 ~ 12 ~ 6 is a cycle of length 3 in Γ(ℤ24).

(2) In general, g(Γ(ℤ4q)) = 4 but g(Γ(ℤ2rq)) = 3 for all primes q ≥ 3 and all integers r ≥ 3. (See Proposition 2.6.)

### Proposition 2.4

If t ≥ 3 is an integer and p1, …, pt are distinct primes, then$g(Γ(ℤp1r1p2r2⋯ptrt))=3$for all positive integers r1, …, rt.

Proof

If t = 3, then $p1r1p2r2~p2r2p3r3~p1r1p3r3~p1r1p2r2$ is a cycle in $Γ(ℤp1r1p2r2p3r3)$; so $g(Γ(ℤp1r1p2r2p3r3))=3$.

If t > 3, then the result follows directly from Lemma 2.2.

### Proposition 2.5

Let p be a prime and r ≥ 2 an integer. Then the following assertions hold.

(1) g(Γ(ℤpr)) = ∞ if and only if pr = 4, 8 or 9.

(2) g(Γ(ℤpr)) = 3 if and only if each of the following conditions holds.

(a) p = 2 and r ≥ 4.

(b) p = 3 and r ≥ 3.

(c) p ≥ 5 and r ≥ 2.

Proof

(1) It is obvious that Γ(ℤ4), Γ(ℤ8) and Γ(ℤ9) have no cycles. Thus the equivalence follows.

(2) If p = 2 and r ≥ 4, then 2r−1, 2r−2, 3 · 2r−2 ∈ Z(ℤ2r). Since the product of any two of them is zero, 2r−1 ~ 2r−2 ~ 3 · 2r−2 ~ 2r−1 is a cycle in Γ(ℤ2r). Thus g(Γ(ℤ2r)) = 3.

If p = 3 and r ≥ 3, then 3r−1, 2 · 3r−1, 3r−2 ∈ Z(ℤ3r). Since the product of any two of them is zero, 3r−1 ~ 2 · 3r−1 ~ 3r−2 ~ 3r−1 is a cycle in Γ(ℤ3r). Thus g(Γ(ℤ3r)) = 3.

If p ≥ 5 and r ≥ 2, then pr−1, 2pr−1, 3pr−1 ∈ Z(ℤpr). Since the product of any two of them is zero, pr−1 ~ 2pr−1 ~ 3pr−1 ~ pr−1 is a cycle in Γ(ℤpr). Thus g(Γ(ℤpr)) = 3.

### Proposition 2.6

Let n be a positive integer which has only two distinct prime divisors. Then the following assertions hold.

(1) g(Γ(ℤn)) = ∞ if and only if n = 2q for some prime q ≥ 3.

(2) g(Γ(ℤn)) = 3 if and only if one of the following holds.

(a) n = 2rqsfor some prime q ≥ 3 and some integers r ≥ 1 and s ≥ 2.

(b) n = 2rq for some prime q ≥ 3 and some integer r ≥ 3.

(c) n = 3rqsfor some prime q ≥ 5 and some integers r ≥ 1 and s ≥ 2.

(d) n = 3rq for some prime q ≥ 5 and some integer r ≥ 2.

(e) n = prqsfor some primes q > p ≥ 5 and some integers r, s ≥ 1 except for r = s = 1.

(3) g(Γ(ℤn)) = 4 if and only if n = pq for some distinct primes p, q ≥ 3, or n = 4q for some prime q ≥ 3.

Proof

(1) If n = 2q for some prime q ≥ 3, then Γ(ℤ2q) is a star graph K1,q−1 by the proof of Theorem 2.1(3). Hence Γ(ℤ2q) has no cycles, and thus g(Γ(ℤ2q)) = ∞.

(2) Let p and q be the only distinct prime divisors of n. Without loss of generality, we may assume that p < q.

Cases (a) and (b)

p = 2. In this case, q ~ 2q ~ 4q ~ q is a cycle of length 3 in Γ(ℤ2q2); so g(Γ(ℤ2q2)) = 3. Hence by Lemma 2.2, g(Γ(ℤ2rqs)) = 3 for all integers r ≥ 1 and s ≥ 2. Also, 4 ~ 2q ~ 4q ~ 4 is a cycle of length 3 in Γ(ℤ8q); so g(Γ(ℤ8q)) = 3. Hence by Lemma 2.2, g(Γ(ℤ2rq)) = 3 for all integers r ≥ 3.

Cases (c) and (d)

p = 3. In this case, q ~ 3q ~ 6q ~ q is a cycle of length 3 in Γ(ℤ3q2); so g(Γ(ℤ3q2)) = 3. Hence by Lemma 2.2, g(Γ(ℤ3rqs)) = 3 for all integers r ≥ 1 and s ≥ 2. Also, 3 ~ 3q ~ 6q ~ 3 is a cycle of length 3 in Γ(ℤ9q); so g(Γ(ℤ9q)) = 3. Hence by Lemma 2.2, g(Γ(ℤ3rq)) = 3 for all integers r ≥ 2.

Case (e)

p ≥ 5. In this case, q ≥ 7; so by Proposition 2.5(2), g(Γ(ℤpr)) = 3 = g(Γ(ℤqs)) for all integers r, s ≥ 2. Hence by Lemma 2.2, g(Γ(ℤprqs)) = 3 for all integers r, s ≥ 1 except for r = s = 1.

(3) If n = pq for some distinct primes p, q ≥ 3, then Γ(ℤpq) is the complete bipartite graph Kp−1,q−1 by the proof of Theorem 2.1(3). Hence there does not exist a cycle of odd length. Note that p ~ 2q ~ 2p ~ q ~ p is a cycle of length 4. Thus g(Γ(ℤpq)) = 4.

Let n = 4q for some prime q ≥ 3, and suppose to the contrary that there exists a cycle a ~ b ~ c ~ a in Γ(ℤ4q). Since ab, bc and ca are divisible by 4q, q divides at least two of a, b and c. Without loss of generality, we may assume that q divides a and b. If 2 divides a, then a = 2q. Since ab is divisible by 4q, b is divisible by 2; so b = 2q. This is absurd. If 2 does not divide a, then a = q or a = 3q. Since 4q divides ab, b is divisible by 4; so b is a multiple of 4q. This is a contradiction. Hence there do not exist cycles of length 3 in Γ(ℤ4q). Note that q ~ 4 ~ 2q ~ 8 ~ q is a cycle of length 4. Thus g(Γ(ℤ4q)) = 4.

In the next remark, we construct a cycle of length 3 in Γ(ℤn) in each case of Proposition 2.6(2).

### Remark 2.7

(1) Let n = 2rqs for some prime q ≥ 3 and some integers r ≥ 1 and s ≥ 2. Then 2rqs−1 ~ 2r+1qs−1 ~ 2r−1qs ~ 2rqs−1 is a cycle of length 3 in Γ(ℤ2rqs).

(2) Let n = 2rq for some prime q ≥ 3 and some integer r ≥ 3. Then 2r ~ 2q ~ 2r−1q ~ 2r is a cycle of length 3 in Γ(ℤ2rq).

(3) Let n = 3rqs for some prime q ≥ 5 and some integers r ≥ 1 and s ≥ 2. Then 3r−1qs ~ 3rqs−1 ~ 2 · 3rqs−1 ~ 3r−1qs is a cycle of length 3 in Γ(ℤ3rqs).

(4) Let n = 3rq for some prime q ≥ 5 and some integer r ≥ 2. Then 3r ~ 3r−1q ~ 2 · 3r−1q ~ 3r is a cycle of length 3 in Γ(ℤ3rq).

(5) Let n = prqs for some primes q > p ≥ 5 and some integers r, s ≥ 1 except for r = s = 1. If r ≠ = 1 and s ≠ = 1, then prqs−1 ~ pr−1qs ~ 2pr−1qs ~ prqs−1 and prqs−1 ~ 2prqs−1 ~ 3prqs−1 ~ prqs−1 are cycles of length 3 in Γ(ℤprqs), respectively.

By Propositions 2.4, 2.5, and 2.6, we obtain

### Theorem 2.8

The following statements hold.

(1) g(Γ(ℤn)) = ∞ if and only if each of the following conditions holds.

(a) n = 4, 8, 9.

(b) n = 2q for some prime q ≥ 3.

(2) g(Γ(ℤn)) = 4 if and only if each of the following conditions holds.

(a) n = pq for some distinct primes p, q ≥ 3.

(b) n = 4q for some prime q ≥ 3.

(3) g(Γ(ℤn)) = 3 in all other cases.

### 3. The Chromatic Number of Γ(ℤn)

In this section, we calculate the chromatic number of Γ(ℤn). Clearly, if there exists a clique in a graph, then the chromatic number of the graph is greater than or equal to the size of the clique; so our method to find the chromatic number of Γ(ℤn) is based on the following three steps:

• Step 1. Find a maximal clique C in Γ(ℤn) and color vertices in C.

• Step 2. Color vertices in Z(ℤn) C by colors used in Step 1.

• Step 3. Confirm that there are no adjacent vertices having the same color.

### Lemma 3.1

If r ≥ 2 is an integer, n = p1 · · · pr for distinct primes p1, …, pr, and$C={npi∣i=1,…,r}$, then C is a maximal clique of Γ(ℤn).

Proof

Note that the product of any two distinct members of C is a multiple of n; so C is a clique. Suppose that there exists an element a ∈ Z(ℤn) C such that ca is a multiple of n for all cC. Then for all i = 1, …, r, pi divides a; so n divides a. This is a contradiction. Thus C is a maximal clique of Γ(ℤn).

### Theorem 3.2

If r ≥ 2 is an integer and n = p1 · · · pr for distinct primes p1, …, pr, then χ(Γ(ℤn)) = r.

Proof

Let $C={npi∣i=1,…,r}$. Then by Lemma 3.1, C is a maximal clique of Γ(ℤn); so the chromatic number of the induced subgraph of Γ(ℤn) induced by C is r. For each i = 1, …, r, let ī be the color of $npi$. Clearly, Z(ℤn) C is nonempty. For each a ∈ Z(ℤn) C, let Sa = {cC | a and c are not adjacent}. Note that by Lemma 3.1, C is a maximal clique; so Sa is a nonempty set. Hence we can find the smallest integer k ∈ {1, …, r} such that a and $npk$are not adjacent. In this case, we color a with .

To complete the proof, we need to check that any two elements in Z(ℤn) with the same color cannot be adjacent. Let a and b be distinct elements in Z(ℤn) with the same color . Since C is a clique, a and b cannot belong to C at the same time. Suppose that aC and b ∈ Z(ℤn) C. Then $a=npk$; so by the coloring of b, a and b are not adjacent. Suppose that a, b ∈ Z(ℤn) C. Then $npka$and $npkb$ are not divisible by n; so neither a nor b is divisible by pk. Therefore ab is not divisible by n, and hence a cannot be adjacent to b. Thus χ(Γ(ℤn)) = r.

### Example 3.3

Consider Γ(ℤ15). Let C = {3, 5}. Then by Theorem 3.2, we color 5 and 3 with 1̄ and 2̄, respectively. Let R = {6, 9, 12} and let vR. Then v is not adjacent to 3; so we color v with 2̄. Note that 10 is not adjacent to 5; so we color 5 with 1̄.

For the detail, see Figure 3. Note that in Figure 3, 1̄ and 2̄ are represented by blue and red, respectively.

### Lemma 3.4

Let$n=p12a1⋯pr2ar$for distinct primes p1, …, pr and positive integers a1, …, ar, and let$C={kn∣k=1,…,n-1}$. Then C is a clique of Γ(ℤn).

Proof

Note that the product of any two distinct elements of C is a multiple of n. Thus C is a clique.

### Theorem 3.5

Let$n=p12a1⋯pr2ar$for distinct primes p1, …, pr and positive integers a1, …, ar. Then$χ(Γ(ℤn))=n-1$.

Proof

Let $C={kn∣k=1,…,n-1}$. Then by Lemma 3.4, C is a clique of Γ(ℤn) with $n-1$ elements. For each $k∈{1,…,n-1}$, let denote the color of $kn$.

Case 1

$n=p12$. In this case, Γ(ℤn) is a complete graph by Theorem 2.1. Hence Z(ℤn) = C. Thus $χ(Γ(ℤn))=n-1$

Case 2

$n≠p12$. In this case, Γ(ℤn) is not a complete graph by Theorem 2.1; so Z(ℤn) C ≠ = ∅︀. Let v ∈ Z(ℤn) C. Then there exists an element m ∈ {1, …, r} such that $pmam$ does not divide v. Take the positive integer sam such that $pms-1$ divides v but $pms$ does not divide v. Then $v((n/pms)n)$ is not a multiple of n; so v and $(n/pms)n$ are not adjacent. We color v with $n/pms$

Now, it remains to check that any two vertices with the same color cannot be adjacent. Let v1 and v2 be distinct elements of Z(ℤn) which have the same color. Since C is a clique, v1 and v2 cannot both belong to C. Suppose that v1C and v2 ∈ Z(ℤn) C. Let $n/pms^$ be the color of v2 for some m ∈ {1, …, r} and s ∈ {1, …, am}. Then v2 is not divisible by $pms$ by the coloring of v2. Since v1C, $v1=(n/pms)n$. Therefore $pm2am$ does not divide v1v2. Hence v1 is not adjacent to v2. Suppose that v1, v2 ∈ Z(ℤn) C, and let $n/pms^$ be the color of v1 and v2 for some m ∈ {1, …, r} and s ∈ {1, …, am}. Then by the coloring of v1 and v2, $pms$ divides neither v1 nor v2; so $pm2s$ does not divide v1v2. Since sam, $pm2am$ does not divide v1v2. Hence v1v2 is not a multiple of n, which means that v1 and v2 are not adjacent.

In either case, Γ(ℤn) is ($(n-1)-colorable$. Note that by Lemma 3.4, $χ(Γ(ℤn))≥n-1$. Thus $χ(Γ(ℤn))=n-1$.

### Example 3.6

Consider Γ(ℤ36). Let C = {6, 12, 18, 24, 30}. Then by Theorem 3.5, we color 6, 12, 18, 24 and 30 with 1̂, 2̂, 3̂, 4̂ and 5̂, respectively. Let R = {2, 4, 8, 10, 14, 16, 20, 22, 26, 28, 32, 34} and let vR. Then v is not divisible by 3; so we color v with 2̂. Let B = {3, 9, 15, 21, 27, 33} and let vB. Then v is not divisible by 2; so we color v with 3̂.

For the detail, see Figure 4. Note that in Figure 4, 1̂, 2̂, 3̂, 4̂ and 5̂ are represented by green, red, blue, pink and brown, respectively.

### Lemma 3.7

Let p1, … , pr, q1, … , qs be distinct primes, a1, … , ar, b1, … , bs nonnegative integers, not all zero, and let $n=p12a1⋯pr2arq12b1+1⋯qs2bs+1$. If$C1={kp1a1⋯prarq1b1+1⋯qsbs+1∣k=1,…,p1a1⋯prarq1b1⋯qsbs-1}$and$C2={p1a1⋯prarq1b1+1⋯qsbs+1/qi∣i=1,…,s}$, then C1 ∪ C2is a maximal clique of Γ(ℤn).

### Proof

We first note that C1C2 = ∅︀. Let C = C1C2. Then for any distinct elements α, βC, αβ is a multiple of n; so C is a clique. Suppose that C is not a maximal clique. Then there exists an element m ∈ Z(ℤn) C such that mc = 0 for all cC. Therefore m is a multiple of $p1a1⋯prarq1b1⋯qi-1bi-1qibi+1qi+1bi+1⋯qsbs$ for all i = 1, …, s. Hence m is a multiple of $p1a1⋯prarq1b1+1⋯qsbs+1$, which implies that mC1. This contradicts the choice of m. Thus C is a maximal clique of Γ(ℤn).

### Theorem 3.8

Let p1, …, pr, q1, …, qs be distinct primes and a1, …, ar, b1, …, bs nonnegative integers, not all zero. If$n=p12a1⋯pr2arq12b1+1⋯qs2bs+1$, then$χ(Γ(ℤn))=p1a1⋯prarq1b1⋯qsbs-1+s$.

### Proof

Let $x=p1a1⋯prarq1b1⋯qsbs$ and $y=p1a1⋯prarq1b1+1⋯qsbs+1$. Then n = xy. Let C1 = {ky | k = 1, …, x−1}, C2 = {y/qi | i = 1, …, s}, and C = C1C2. Then by Lemma 3.7, C is a maximal clique of Γ(ℤn). For each k = 1, …, x − 1, let be the color of ky and for each i = 1, …, s, let ī be the color of y/qi. Note that by Theorem 2.1, Γ(ℤn) is not a complete graph. Let v ∈ Z(ℤn) C.

Case 1

There exists an element cC1 which is not adjacent to v. In this case, v is not divisible by x. If $q1b1⋯qsbs$ divides v, then $pmam$ does not divide v for some m ∈ {1, …, r}; so we can take the positive integer αam such that $pmα-1$ divides v but $pmα$ does not divide v. Hence v is not adjacent to $(x/pmα)y$. We color v with $x/pmα^$. If $qtbt$ does not divide v for some t ∈ {1, …, s}, then we can find the positive integer βbt such that $qtβ-1$ divides v but $qtβ$ does not divide v. Hence v is not adjacent to $(x/qtβ)y$. We color v with $x/qtβ^$.

Case 2

v is adjacent to c for all cC1. In this case, v is a multiple of x. If $q1b1+1⋯qsbs+1$ divides v, then vC1, which is a contradiction to the choice of v. Therefore we can find an element i ∈ {1, …, s} such that $qibi$ divides v but $qibi+1$ does not divide v. Clearly, v(y/qi) is not a multiple of n. Hence v and y/qi are not adjacent. We color v with ī.

It remains to show that there are no adjacent vertices with the same color. Let v1, v2 ∈ Z(ℤn) have the same color. Since C is a clique, at least one of v1 and v2 does not belong to C. Suppose that v1C but v2 ∈ Z(ℤn) C. If the color of v1 and v2 is $x/pmα^$ for some m ∈ {1, …, r} and α ∈ {1, …, am}, then by the coloring of v1 and v2, $v1=(x/pmα)y$ and $pmα$ does not divide v2; so v1v2 is not a multiple of n. Hence v1 is not adjacent to v2. If the color of v1 and v2 is $x/qtβ^$ for some t ∈ {1, …, s} and β ∈ {1, …, bt}, then by the coloring of v1 and v2, $v1=(x/qtβ)y$ and $qtβ$ does not divide v2; so v1v2 is not a multiple of n. Hence v1 is not adjacent to v2. If ī is the color of v1 and v2 for some i ∈ {1, …, s}, then v1 = y/qi and so by the coloring of v2, v1 and v2 are not adjacent. We next suppose that v1, v2 ∈ Z(ℤn) C. If $x/pmα^$ is the color of v1 and v2 for some m ∈ {1, …, r} and α ∈ {1, …, am}, then by Case 1, $pmα$ divides neither v1 nor v2; so $pm2am$ does not divide v1v2. Hence v1 and v2 are not adjacent. If $x/qtβ^$ is the color of v1 and v2 for some t ∈ {1, …, s} and β ∈ {1, …, bt}, then by Case 1, $qtβ$ divides neither v1 nor v2; so $qt2bt$ does not divide v1v2. Hence v1 and v2 are not adjacent. If ī is the color of v1 and v2 for some i ∈ {1, …, s}, then by Case 2, $qibi+1$ divides neither v1 nor v2. Hence $qi2bi+1$ cannot divide v1v2, which means that v1 and v2 are not adjacent. Consequently, Γ(ℤn) is ($(p1a1⋯prarq1b1⋯qsbs-1+s)-colorable$. Note that by Lemma 3.7, $χ(Γ(ℤn))≥p1a1⋯prarq1b1⋯qsbs-1+s$. Thus $χ(Γ(ℤn))=p1a1⋯prarq1b1⋯qsbs-1+s$.

### Example 3.9

Consider Γ(ℤ18). Let C1 = {6, 12} and C2 = {3}. Then by Theorem 3.8, we color 6, 12 and 3 with 1̂, 2̂ and 1̄, respectively. Let R = {2, 4, 8, 10, 14, 16} and let vR. Then v is not adjacent to 6. Note that v is not divisible by 3; so we color v with 1̂. Let B = {9, 15} and let vB. Then v is adjacent to all elements in C1. Note that v is not divisible by 2; so we color v with 1̄.

For the detail, see Figure 5. Note that in Figure 5, 1̂, 2̂ and 1̄ are represented by red, green and blue, respectively.

### Example 3.10

Consider Γ(ℤ72). Let C1 = {12, 24, 36, 48, 60} and C2 = {6}. Then by Theorem 3.6, we color 6, 12, 24, 36, 48 and 60 with 1̄, 1̂, 2̂, 3̂, 4̂ and 5̂, respectively. Let P = {2, 4, 8, 10, 14, 16, 20, 22, 26, 28, 32, 34, 38, 40, 44, 46, 50, 52, 56, 58, 62, 64, 68, 70} and let vP. Then v is not adjacent to 12. Note that v is a multiple of 2 but not a multiple of 3; so we color v with 2̂. Let B = {3, 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69} and let vB. Then v is not adjacent to 12. Note that v is not divisible by 2; so we color v with 3̂. Let Y = {18, 30, 42, 54, 66} and let vY. Then v is adjacent to all elements in C1. Since v and 6 are not adjacent, we color v with 1̄.

For the detail, see Figure 6. Note that in Figure 6, 1̄, 1̂, 2̂, 3̂, 4̂ and 5̂ are represented by yellow, red, pink, blue, sky-blue and green, respectively.

### Acknowledgements

The authors would like to thank the referee for his/her several valuable suggestions. The third author was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2017R1C1B1008085).

Fig. 1. The diameters of some zero-divisor graphs
Fig. 2. The girth of some zero-divisor graphs
Fig. 3. The coloring of Γ(ℤ15)
Fig. 4. The coloring of Γ(ℤ36)
Fig. 5. The coloring of Γ(ℤ18)
Fig. 6. The coloring of Γ(ℤ72)
1. DF. Anderson, MC. Axtell, and JA. Stickles. Zero-divisor graphs in commutative rings. Commutative Algebra: Noetherian and Non-Noetherian Perspectives, , Springer, New York, 2011:23-45.
2. DF. Anderson, and PS. Livingston. The zero-divisor graph of a commutative ring. J Algebra., 217(1999), 434-447.
3. DD. Anderson, and M. Naseer. Beck’s coloring of a commutative ring. J Algebra., 159(1993), 500-514.
4. I. Beck. Coloring of commutative rings. J Algebra., 116(1988), 208-226.
5. S. Mulay. Cycles and symmetries of zero-divisors. Comm Algebra., 30(2002), 3533-3558.