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 exists 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 K_n. 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. 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. A maximal clique in G is a clique that cannot be extended by including one more adjacent vertex. The clique number of G, denoted by cl(G), is the greatest integer $n\ge 1$ such that $K_n\subseteq G$. If $K_n\subseteq G$ for all integers $n\ge 1$, then cl(G) is defined to be ∞. It is easy to see that $\chi (G)\ge \text{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 the 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 [6], Beck first introduced the concept of the zero-divisor graph of a commutative ring and in [3], Anderson and Naseer continued to study. In [3] and [6], all elements of R are vertices of the graph and the authors were mainly interested in graph coloring. 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]. In [8,(1.4)], Mulay proved that g(Γ(R)) ≤ 4. In [5], the authors studied the zero-divisor graphs of polynomial rings and power series rings.

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

Let ${\mathbb{Z}}_n$ be the ring of integers modulo n and let ${\mathbb{Z}}_n[X]$ (resp., ${\mathbb{Z}}_n[\text{}[X]\text{}]$) be the polynomial ring (resp., power series ring) over ${\mathbb{Z}}_n$. Let ${\mathbb{Z}}_n[X]\text{}]$ be either ${\mathbb{Z}}_n[X]$ or ${\mathbb{Z}}_n[\text{}[X]\text{}]$. In [9], the authors studied the zero-divisor graph of ${\mathbb{Z}}_n$. In fact, they completely characterized the diameter, the girth and the chromatic number of $\Gamma ({\mathbb{Z}}_n)$. The purpose of this paper is to study some properties of the zero-divisor graph of ${\mathbb{Z}}_n[X]\text{}]$. If n is a prime number, then ${\mathbb{Z}}_n[X]\text{}]$ has no zero-divisors; so $\Gamma ({\mathbb{Z}}_n[X]\text{}])$ 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 $\Gamma ({\mathbb{Z}}_n[X]\text{}])$. In Section 3, we calculate the chromatic number of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$. Note that all figures are drawn via website http://graphonline.ru/en/.

In order to give the complete characterization of the diameter of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$, we need the following lemma.

Lemma 2.1. ([4, Chapter 1, Exercise 2(iii)] and [7, Theorem 5])

Let R be a commutative ring with identity. Then the following assertions hold.

• (1) If $f\in \text{Z}(R[X])$, then there exists a nonzero element r ∈ R such that rf=0.

• (2) If R is a Noetherian ring and $f\in \text{Z}(R[\text{}[X]\text{}])$, then there exists a nonzero element r ∈ R such that rf=0.

Let R be a commutative ring with identity. For a nonempty subset C of R, let $C[X]\text{}]$ be the subset of $R[X]\text{}]$ consisting of elements whose coefficients belong to C. For an element $f={\displaystyle \sum _{i\ge 0}{a}_i}{X}^i\in R[X]\text{}]$, the order of f is defined to be the smallest nonnegative integer n such that $a_n\ne 0$ and is denoted by ord(f).

Theorem 2.2.

The following statements hold.

• (1) $\text{diam}(\Gamma ({\mathbb{Z}}_n[X]\text{}]))=1$ if (and only if) n=p² for some prime p.

• (2) $\text{diam}(\Gamma ({\mathbb{Z}}_n[X]\text{}]))=2$ if (and only if) n=p^r for some prime p and some integer r ≥ 3, or n=pq for some distinct primes p and q.

• (3) $\text{diam}(\Gamma ({\mathbb{Z}}_n[X]\text{}]))=3$ if (and only if) n=pqr for some distinct primes p, q and some integer r ≥ 2.

Proof. Before proving the result, we note that for all integers $n\ge 2$, ${\mathbb{Z}}_n$ is a Noetherian ring.

(1) Suppose that n=p^r for some prime p and some integer r ≥ 3. Let f and g be two distinct elements of $\text{Z}({\mathbb{Z}}_{p^2}[X]\text{}])$. Then by Lemma 2.1, f and g are elements of $\text{Z}({\mathbb{Z}}_{p^2})[X]\text{}]$. Note that $\text{Z}({\mathbb{Z}}_{p^2})=\{p,2p,\dots ,(p-1)p\}$; so the product of any two elements of $\text{Z}({\mathbb{Z}}_{p^2})$ is zero. Hence fg=0 in ${\mathbb{Z}}_{p^2}[X]\text{}]$. This indicates that $\Gamma ({\mathbb{Z}}_{p^2}[X]\text{}])$ is a complete graph. Thus $\text{diam}(\Gamma ({\mathbb{Z}}_{p^2}[X]\text{}]))=1$.

(2) Suppose that n=p^r, where p is a prime and r is an integer greater than or equal to 3. Let f and g be two distinct elements of $\text{Z}({\mathbb{Z}}_{p^r}[X]\text{}])$. Then by Lemma 2.1, f and g are elements of $\text{Z}({\mathbb{Z}}_{p^r})[X]\text{}]$. Note that $\text{Z}({\mathbb{Z}}_{p^r})=\{p,2p,\dots ,(p^{r-1}-1)p\}$; so for all $a\in \text{Z}({\mathbb{Z}}_{p^r})$, $a{p}^{r-1}=0$ in ${\mathbb{Z}}_{p^r}$. Hence $f-p^{r-1}-g$ is a path in $\Gamma ({\mathbb{Z}}_{p^r}[X]\text{}])$, which implies that $\text{diam}(\Gamma ({\mathbb{Z}}_{p^r}[X]\text{}]))\le 2$. Thus $\text{diam}(\Gamma ({\mathbb{Z}}_{p^r}[X]\text{}]))=2$.

Suppose that n=pq, where p and q are distinct primes. Let $A=\{p,2p,\dots ,(q-1)p\}$ and $B=\{q,2q,\dots ,(p-1)q\}$. Then $A\cap B=\varnothing$ and $\text{Z}({\mathbb{Z}}_{pq})=A\cup B$. Let $f\in \text{Z}({\mathbb{Z}}_{pq}[X]\text{}])$. Then by Lemma 2.1, there exists an element $r\in \text{Z}({\mathbb{Z}}_{pq})$ such that rf=0. Note that for any $a_1,a_2\in A$ and $b_1,b_2\in B$, $a_1{a}_2\ne 0$ and $b_1{b}_2\ne 0$ in ${\mathbb{Z}}_{pq}$; so if r ∈ A (resp., r ∈ B), then $f\in B[X]\text{}]$ (resp., $f\in A[X]\text{}]$). Therefore $\text{Z}({\mathbb{Z}}_{pq}[X]\text{}])=A[X]\text{}]\cup B[X]\text{}]$. Note that $A[X]\text{}]\cap B[X]\text{}]=\varnothing$ and for any a ∈ A and b ∈ B, ab=0. Hence $\Gamma ({\mathbb{Z}}_{pq}[X]\text{}])$ is a complete bipartite graph. Thus $\text{diam}(\Gamma ({\mathbb{Z}}_{pq}[X]\text{}]))=2$.

(3) Suppose that n=pqr, where p, q are distinct primes and r is an integer greater than or equal to 2. Then $pX,qX\in \text{Z}({\mathbb{Z}}_{pqr}[X]\text{}])$ with $(pX)(qX)\ne 0$ in ${\mathbb{Z}}_{pqr}[X]\text{}]$; so $\text{diam}(\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}]))\ge 2$. Suppose to the contrary that there exists an element $f\in \text{Z}({\mathbb{Z}}_{pqr}[X]\text{}])$ such that $pX-f-qX$ is a path in $\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}])$. Let a be the coefficient of $X^{\text{ord}(f)}$ in f. Then ap=0=aq in ${\mathbb{Z}}_{pqr}$; so a is a multiple of pqr. Therefore a=0 in ${\mathbb{Z}}_{pqr}$. This is absurd. Hence $\text{diam}(\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}]))\ge 3$. Thus $\text{diam}(\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}]))=3$ [2,Theorem 2.3].

Figure 1. The diameter of some zero-divisor graphs

We next study the girth of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$.

Proposition 2.3.

If p is a prime and r ≥ 2 is an integer, then $\text{g}(\Gamma ({\mathbb{Z}}_{p^r}[X]\text{}]))=3$.

Proof. It suffices to note that $p^{r-1}-p^{r-1}X-p^{r-1}{X}^2-p^{r-1}$ is a cycle of length 3 in $\Gamma ({\mathbb{Z}}_{p^r}[X]\text{}])$.

Proposition 2.4.

If p and q are distinct primes, then $\text{g}(\Gamma ({\mathbb{Z}}_{pq}[X]\text{}]))=4$.

Proof. Note that by the proof of Theorem 2.2(2), $\Gamma ({\mathbb{Z}}_{pq}[X]\text{}])$ is a complete bipartite graph; so $\Gamma ({\mathbb{Z}}_{pq}[X]\text{}])$ does not have a cycle of length 3. Let A and B be as in the proof of Theorem 2.2(2). Then for any f ∈ A[X] and g ∈ B[X], pX-g-f-qX-pX is a cycle of length 4 in $\Gamma ({\mathbb{Z}}_{pq}[X]\text{}])$. Thus $\text{g}(\Gamma ({\mathbb{Z}}_{pq}[X]\text{}]))=4$.

Lemma 2.5.

If $\text{g}(\Gamma ({\mathbb{Z}}_n[X]\text{}]))=3$, then $\text{g}(\Gamma ({\mathbb{Z}}_{mn}[X]\text{}]))=3$ for all integers $m\ge 1$.

Proof. Let m be any positive integer. Note that if f-g-h-f is a cycle of length 3 in $\Gamma ({\mathbb{Z}}_n[X]\text{}])$, then mf-mg-mh-mf is a cycle of length 3 in $\Gamma ({\mathbb{Z}}_{mn}[X]\text{}])$. Thus $\text{g}(\Gamma ({\mathbb{Z}}_{mn}[X]\text{}]))=3$.

Lemma 2.6.

Let p and q be distinct primes. Then $\text{g}(\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}]))=3$ for any prime r.

Proof. If r=p, then p-pq-pqX-p is a cycle of length 3 in $\Gamma ({\mathbb{Z}}_{p^{2}q}[X]\text{}])$. If r=q, then q-pq-pqX-q is a cycle of length 3 in $\Gamma ({\mathbb{Z}}_{p{q}^2}[X]\text{}])$. Suppose that r ≠ p and r ≠ q. Then pq-qr-pr-pq is a cycle of length 3 in $\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}])$. Thus $\text{g}(\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}]))=3$ for any prime r.

Proposition 2.7.

Let p and q be distinct primes. Then $\text{g}(\Gamma ({\mathbb{Z}}_{pqr}[X]\text{}]))=3$ for any integer r ≥ 2.

Proof. Note that r is a multiple of some prime. Thus the result follows directly from Lemmas 2.5 and 2.6.

By Propositions 2.3, 2.4 and 2.7, we can completely characterize the girth of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$ as follows:

Theorem 2.8.

The following statements hold.

• (1) $\text{g}(\Gamma ({\mathbb{Z}}_n[X]\text{}]))=3$ if (and only if) each of the following conditions holds.

  • (a) n=p^r for some prime p and integer r ≥ 2.

  • (b) n=pqr for some distinct primes p, q and integer r ≥ 2.

• (2) $\text{g}(\Gamma ({\mathbb{Z}}_n[X]\text{}]))=4$ if (and only if) n=pq for some distinct primes p and q.

Figure 2. The girth of some zero-divisor graphs

In this section, we calculate the chromatic number of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$. 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. Hence in order to find the chromatic number of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$, we investigate to find a (maximal) clique of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$.

Lemma 3.1.

If r ≥ 2 is an integer, $n=p_1\cdots p_r$ for distinct primes $p_1,\dots ,p_r$, and $C=\left\{\frac{n}{p_i}\right|i=1,\dots ,r\}$, then C is a maximal clique of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$.

Proof. Note that the product of any two distinct members of C is zero in ${\mathbb{Z}}_n[X]\text{}]$; so C is a clique. Suppose to the contrary that there exists an element $f\in \text{Z}({\mathbb{Z}}_n[X]\text{}])\setminus C$ such that cf=0 in ${\mathbb{Z}}_n[X]\text{}]$ for all c ∈ C. Let a be the coefficient of $X^{\text{ord}(f)}$ in $f$. Then ca=0 in ${\mathbb{Z}}_n$; so $a$ is a multiple of p_i for all $i=1,\dots ,r$. Hence a is a multiple of n, i.e., a=0 in ${\mathbb{Z}}_n$. This is a contradiction. Thus C is a maximal clique of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$.

Proposition 3.2.

If $r\ge 2$ is an integer and $n=p_1\cdots p_r$ for distinct primes $p_1,\dots ,p_r$, then $\chi (\Gamma ({\mathbb{Z}}_n[X]\text{}]))=r$.

Proof. Let $C=\left\{\frac{n}{p_i}\right|i=1,\dots ,r\}$. Then by Lemma 3.1, C is a maximal clique of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$. For each $i=1,\dots ,r$, let $\overline{i}$ be the color of $\frac{n}{p_i}$. Clearly, $\text{Z}({\mathbb{Z}}_n[X]\text{}])\setminus C$ is a nonempty set. For each $f\in \text{Z}({\mathbb{Z}}_n[X]\text{}])\setminus C$, let $S_f=\{c\in C|f$ and c are not adjacent}. Then by Lemma 3.1, C is a maximal clique of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$; so S_f is a nonempty set. Hence we can find the smallest integer $k\in \{1,\dots ,r\}$ such that $\frac{n}{p_k}\in S_f$. In this case, we color f with $\overline{k}$.

To complete the proof, it remains to check that any two vertices of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$ with the same color cannot be adjacent. Fix an element $k\in \{1,\dots ,r\}$ and let f and g be distinct vertices of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$ with the same color $\stackrel{-}{k}$. Since C is a clique, f and g cannot belong to C at the same time. Suppose that f ∈ C and $g\in \text{Z}({\mathbb{Z}}_n[X]\text{}])\setminus C$. Then $f=\frac{n}{p_k}$; so by the coloring of g, f and g are not adjacent. Suppose that $f,g\in \text{Z}({\mathbb{Z}}_n[X]\text{}])\setminus C$ and write $f={\displaystyle \sum _{i\ge 0}{a}_i}{X}^i$ and $g={\displaystyle \sum _{i\ge 0}{b}_i}{X}^i$. Then by the coloring of f and g, f and g are not adjacent to $\frac{n}{p_k}$; so $\frac{n}{p_k}f\ne 0$ and $\frac{n}{p_k}g\ne 0$ in ${\mathbb{Z}}_n[X]\text{}]$. Let α be the smallest nonnegative integer such that $\frac{n}{p_k}{a}_{\alpha }\ne 0$ in ${\mathbb{Z}}_n$ and let β be the smallest nonnegative integer such that $\frac{n}{p_k}{b}_{\beta }\ne 0$ in ${\mathbb{Z}}_n$. Then $a_0,\dots ,a_{\alpha -1},b_0,\dots ,b_{\beta -1}$ are divided by p_k and $a_{\alpha },b_{\beta }$ are not divided by p_k; so the coefficient of $X^{\alpha +\beta }$ in fg is not divided by p_k. Therefore $fg\ne 0$ in ${\mathbb{Z}}_n[X]\text{}]$. Hence f and g are not adjacent.

Thus we conclude that $\chi (\Gamma ({\mathbb{Z}}_n[X]\text{}]))=r$.

We denote the set of nonnegative integers by ${\mathbb{N}}_0$.

Lemma 3.3.

If n is a multiple of the square of a prime, then $\Gamma ({\mathbb{Z}}_n[X]\text{}])$ has an infinite clique.

Proof. Suppose that n is a multiple of the square of a prime.

Case 1. $n=p_1^{2a_1}\cdots p_r^{2a_r}$ for distinct primes $p_1,\dots ,p_r$ and positive integers $a_1,\dots ,a_r$. In this case, let $C=\left\{\sqrt{n}{X}^m\right|m\in {\mathbb{N}}_0\}$. Then the product of any two elements of C is zero in ${\mathbb{Z}}_n[X]\text{}]$; so C is an infinite clique of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$.

Case 2. $n=p_1^{2a_1}\cdots p_r^{2a_r}{q}_1^{2b_1+1}\cdots q_s^{2b_s+1}$ for distinct primes $p_1,\dots ,p_r,$ $q_1,\dots ,q_s$ and nonnegative integers $a_1,\dots ,a_r,b_1,\dots ,b_s$, not all zero. In this case, let $k=p_1^{a_1}\cdots p_r^{a_r}{q}_1^{b_1+1}\cdots q_s^{b_s+1}$ and let $C=\left\{k{X}^m\right|m\in {\mathbb{N}}_0\}$. Then the product of any two elements of C is zero in ${\mathbb{Z}}_n[X]\text{}]$; so C is an infinite clique of $\Gamma ({\mathbb{Z}}_n[X]\text{}])$.

By Cases 1 and 2, $\Gamma ({\mathbb{Z}}_n[X]\text{}])$ has an infinite clique.

Proposition 3.4.

Let n be a multiple of the square of a prime. Then $\chi (\Gamma ({\mathbb{Z}}_n[X]\text{}]))=\infty$.

Proof. By Lemma 3.3, $\Gamma ({\mathbb{Z}}_n[X]\text{}])$ has an infinite clique; so $\text{cl}(\Gamma ({\mathbb{Z}}_n[X]\text{}]))=\infty$.

Thus $\chi (\Gamma ({\mathbb{Z}}_n[X]\text{}]))=\infty$.

By Propositions 3.2 and 3.4, we obtain the main result in this section.

Theorem 3.5.

The following statements hold.

• (1) $\chi (\Gamma ({\mathbb{Z}}_n[X]\text{}]))=r$ if (and only if) $n=p_1\cdots p_r$ for some distinct primes $p_1,\dots ,p_r$.

• (2) $\chi (\Gamma ({\mathbb{Z}}_n[X]\text{}]))=\infty$ if (and only if) n is a multiple of the square of some prime.

Figure 3. The coloring of some zero-divisor graphs

We would like to thank the referee for several valuable suggestions.