The article, Zero-Divisor Graphs of \mathbb{Z}_n and Polynomial Quotient Rings over \mathbb{Z}_n, by Daniel Endean, Kristin Henry, and Erin Manlove discusses the necessity of knowing the chromatic number of a graph as well as if it is perfect in order to understand it. It also shows several different ways that you can know when the zero-divisor graph of \mathbb{Z}_N (\Gamma(\mathbb{Z}_n)) s perfect. In its final section, the article proves that \Gamma(\mathbb{Z}_p [x]\slash<x^n>) \cong \Gamma(\mathbb{Z}_{p^n}).

The introduction of the article provides numerous definitions. For instance, a graph G is the set of vertices V(G) with a corresponding set of edges E(G) where every element in E(G) is an unordered pair of distinct vertices from V(G). The order of G is the cardinality of G, or the number of elements it contains, and is denoted |G|. The chromatic number of G is the minimum number of colors required to color G so that no adjacent vertices have the same color, and is denoted \chi(G). Furthermore, when all of the vertices of G touch, G is complete. We say that H is a subgraph of G if V(H)\subseteq V(G) and E(H)\subseteq E(G). A clique is a complete subgraph, and the clique number of a graph, denoted \omega(G), is the order of the larget clique of G. The article then moves on to discuss the ways in which \chi(G) can be derived.

Two different processes for finding \chi(G) are presented. The first is fairly straight forward. You simply find the chromatic number, and then prove that a smaller number of colors would be insufficient for the graph to be complete. The second involves showing that a graph is perfect, so that the graphs clique number can be used to find its chromatic number. According to the article, a graph is perfect if all of its subgraphs have the same chromatic number and clique number. Several theorems and corresponding proofs are provided which give specific examples of perfect graphs. Theorem 1.1 states than any graph that has no subgraphs with alternating edges and vertices is perfect. Theorem 1.2 says that for prime p, the graph \Gamma(\mathbb{Z}_{p^n}) is perfect. Theorem 1.3 states that for distinct primes p_1 and p_2, the graph \Gamma(\mathbb{Z}_{p_1p_2}) is perfect. Finally, Theorem 1.4 says that the zero-divisor graph of \mathbb{Z}_n is perfect if and only if n=p^k where p is prime or n=p_1p_2 where p_1 and p_2 are distinct primes. The last two theorems of this section show how, given a perfect graph, the chromatic number can be found using the graph’s clique number. Theorem 1.5 states that for prime p, the graph \Gamma(\mathbb{Z}_{p^n}) has chromatic number p^{\dfrac{n}{2}}-1 when n is even and p^{\dfrac{n-1}{2}} when n is odd. Finally, Theorem 1.6 says that for distinct primes p_1 and p_2, the graph \Gamma(\mathbb{Z}_{p_1p_2}) has chromatic number two.

The next section of the paper addresses zero-divisor graphs of polynomial quotient rings and defines Q such that Q=\mathbb{Z}_p[x]\slash<x^n> where p is prime and n \geq 2. The paper then uses various theorems, corollaries,  lemmas, and proofs to arrive at its final conclusion: \Gamma(\mathbb{Z}_{p^n}) \cong \Gamma(Q).

Advertisements