WEAKLY PERFECT GRAPHS ARISING FROM RINGS

H. R. MAIMANI, M. R. POURNAKI, AND S. YASSEMI

Abstract. A graph is called weakly perfect if its chromatic number equals its clique number. In this paper a new class of weakly perfect graphs arising from rings are presented and an explicit formula for the chromatic number of such graphs is given.

1. Introduction

Throughout the paper by a graph we mean a finite undirected graph without loops or multiple edges. Also, all rings are finite commutative with non-zero identity. For undefined terms and concepts, the reader is referred to [5] and [2]. Let k be a positive integer. For a graph G, a k-colouring of the vertices of G is an assignment of k colours to the vertices of G in such a way that no two adjacent vertices receive the same colour. The chromatic number of G, denoted by χ(G), is the smallest number k such that G admits a k-colouring. A clique in G is a set of pairwise adjacent vertices of G. A clique of the maximum size is called a maximum clique. The clique number of G, denoted by ω(G), is the number of vertices of a maximum clique in G. The parameters χ(G) and ω(G) have been extensively studied by many authors. It is easy to see that χ(G) ≥ ω(G), because every vertex of a clique should get a different colour. It is also easy to see that χ(G) may be larger than ω(G). For example, χ(C_{5}) = 3 > 2 = ω(C_{5}), where C_{5} is a cycle of length five. Therefore, it is natural to consider the case in which χ(G) is equal to ω(G). In this direction, a graph G is called weakly perfect provided χ(G) = ω(G).

In this paper a new class of weakly perfect graphs arising from rings are presented. Moreover, the proof gives us an explicit formula for the chromatic number of such graphs.

2. Unit graphs

Let n be a positive integer and ℤ_{n} be the ring of integers modulo n. Ralph P. Grimaldi [3] defined a graph G(ℤ_{n}) based on the elements and units of ℤ_{n}. The vertices of G(ℤ_{n}) are the elements of ℤ_{n} and distinct vertices x and y are defined to be adjacent if and only if x+y is a unit of ℤ_{n}. For a positive integer m, it follows that G(ℤ_{2m}) is a φ(2m)-regular graph, where φ is the Euler phi function. In case m ≥ 2, G(ℤ_{2m}) can be expressed as the union of φ(2m)/2 Hamiltonian cycles. The odd case is not very easy, but the structure is clear and the results are similar to the even case. We recall that a cone over a graph is obtained by taking the categorical product of the graph and a path with a loop at one end, and then identifying all the vertices whose second coordinate is the other end of the path. When p is an odd prime, G(ℤ_{p}) can be expressed as a cone over a complete partite graph with (p − 1)/2 partitions of size two. This leads to an explicit formula for the chromatic polynomial of G(ℤ_{p}). The paper [3] also concludes with some properties of the graphs G(ℤ_{p^{m}}), where p is a prime number and m ≥ 2.

2000 Mathematics Subject Classification. Primary 05C15, 05C69, 05C17; Secondary 13M05.

Key words and phrases. Chromatic number, Clique number, Weakly perfect graph, Finite ring.

The research of the authors was in part supported by a grant from IPM (No. 88050214, No.

88130113 and No. 88130213).

Recently, Ashrafi et al. [1] generalized G(ℤ_{n}) to G(R), the unit graph of R, where R is an arbitrary ring and studied the properties of this graph. Let us first define this notion.

Definition 2.1. Let R be a ring and U(R) be the set of unit elements of R. The unit graph of R, denoted by G(R), is the graph obtained by setting all the elements of R to be the vertices and defining distinct vertices x and y to be adjacent if and only if x + y ∈ U(R).

The graphs in Figure 1 are the unit graphs of the rings indicated.

[figure: 0; 1; 2; G(ℤ_{3}); 0; 1; 2; 3; G(ℤ_{4}); 10; 11; 00; 01; G(ℤ_{2} × ℤ_{2})]

Figure 1. The unit graphs of some specific rings.

It is easy to see that, for given rings R and S, if R ≅ S as rings, then G(R) ≅ G(S) as graphs. This point is illustrated in Figure 2 for the unit graphs of two isomorphic rings ℤ_{3} × ℤ_{2} and ℤ_{6}.

[figure: 00; 11; 21; 10; 20; 01; G(ℤ_{3} × ℤ_{2}); ≅; 0; 5; 1; 2; 4; 3; G(ℤ_{6})]

Figure 2. The unit graphs of two isomorphic rings.

The main result of this paper (see Theorem 2.2) shows that the unit graphs are weakly perfect. Also the proof of Theorem 2.2 gives us an explicit formula for the chromatic number of such graphs.

Theorem 2.2. If R is a ring, then the unit graph G(R) is weakly perfect.

3. The proofs

In this section we state and prove some lemmas that will be used in the proof of Theorem 2.2. Furthermore, for the convenience of the reader, we state without proof a few known results in the form of propositions which will be used in the proofs of the lemmas. We also recall some definitions and notations concerning graphs for later use.

We start with the following proposition. Let us recall that an independent set of vertices (also called a coclique) in a graph is a set of pairwise non-adjacent vertices.

Proposition 3.1 ([1], Lemma 2.7). Let R be a ring and suppose that J(R) denotes the Jacobson radical of R. If x, y ∈ R, then the following statements hold:

(a) If x + J(R) and y + J(R) are adjacent in the unit graph G(R/J(R)), then every element of x + J(R) is adjacent to every element of y + J(R) in the unit graph G(R).

(b) If 2x ∈ U(R), then x + J(R) is a clique in the unit graph G(R).

(c) If 2x ∉ U(R), then x + J(R) is a coclique in the unit graph G(R).

We are now ready to state and prove the following two lemmas which give us some information about the cliques and colouring of the unit graph G(R) by using the unit graph G(R/J(R)).

Lemma 3.2. Let R be a ring and suppose that 2 + J(R) ∈ U(R/J(R)), where J(R) denotes the Jacobson radical of R. Also let k and ℓ be positive integers. Then the following statements hold:

(a) If the unit graph G(R/J(R)) has a clique of size k + ℓ with exactly ℓ non-unit elements, then the unit graph G(R) has a clique of size |J(R)|k + ℓ.

(b) If the unit graph G(R/J(R)) admits a (k+ℓ)-colouring, among which exactly ℓ colours are used to colour non-unit elements, then the unit graph G(R) admits a (|J(R)|k + ℓ)-colouring.

Proof. For the proof of part (a), by the assumption we may assume that

S = {x_{1} + J(R), …, x_{k} + J(R), y_{1} + J(R), …, y_{ℓ} + J(R)}

is a clique in G(R/J(R)) in such a way that, for every i with 1 ≤ i ≤ k, x_{i} + J(R) is a unit element of R/J(R) and, for every j with 1 ≤ j ≤ ℓ, y_{j} + J(R) is a non-unit element of R/J(R).

Suppose that x_{i} + J(R), 1 ≤ i ≤ k, is given. Since 2 + J(R) and x_{i} + J(R) are unit elements in R/J(R), (2+J(R))(x_{i} +J(R)) = 2x_{i} +J(R) ∈ U(R/J(R)), and therefore there exists t ∈ R such that (2x_{i} + J(R))(t + J(R)) = 1 + J(R). This implies that 2x_{i}t − 1 ∈ J(R). Now suppose, on the contrary, that 2x_{i} is not a unit element in R. Therefore, ⟨2x_{i}⟩ is a proper ideal of R, and so there exists a maximal ideal 𝔪 of R such that ⟨2x_{i}⟩ ⊆ 𝔪. Thus 2x_{i} ∈ 𝔪, and so 2x_{i}t ∈ 𝔪. On the other hand, 2x_{i}t − 1 ∈ 𝔪, which implies that 1 ∈ 𝔪, a contradiction. Thus 2x_{i} ∈ U(R), and therefore, by part (b) of Proposition 3.1, x_{i} + J(R) is a clique in G(R).

Now suppose that y_{j} + J(R), 1 ≤ j ≤ ℓ, is given. Since y_{j} + J(R) is not a unit element in R/J(R), it is easy to see that 2y_{j} ∉ U(R), and thus, by part (c) of Proposition 3.1, y_{j} + J(R) is a coclique in G(R).

Also, by part (a) of Proposition 3.1, if a+J(R) and b+J(R) are two distinct cosets in S, then every element of a+J(R) is adjacent to every element of b+J(R) in G(R).

Therefore, we conclude that the set ∪_{i=1}^{k}(x_{i} + J(R)) ∪ {y_{1}, …, y_{ℓ}} is a clique in G(R) of size ∑_{i=1}^{k} |x_{i} + J(R)| + ℓ = ∑_{i=1}^{k} |J(R)| + ℓ = |J(R)|k + ℓ. Therefore, the requested clique in G(R) exists.

For the proof of part (b), consider J(R) = {r_{1}, …, r_{|J(R)|}} and note that, by Proposition 3.1, every coset of R/J(R) is either a clique or a coclique in G(R). Suppose that x ∈ R is given. We want to colour the vertex x. Since the distinct cosets of R/J(R) form a partition of R, we may assume that x belongs to a + J(R) which has colour α. There are two possibilities: either a + J(R) is a clique or is a coclique in G(R). If the first case occurs, write x = a + r_{i}, r_{i} ∈ J(R) and colour x by (α, r_{i}). If the second case occurs, write colour x by α.

We now show that this is a colouring of vertices of G(R). In order to do this, suppose that distinct vertices x and y are adjacent in G(R). There are two possibilities: either x and y belong to one coset or x and y belong to different cosets.

First, suppose that x and y belong to one coset, say a + J(R), which has colour α. Since x is adjacent to y in G(R), a + J(R) is a clique in G(R/J(R)). We may write x = a + r_{i} and y = a + r_{j}, where r_{i} ≠ r_{j}. Therefore, x has colour (α, r_{i}), while y has the different colour, namely (α, r_{j}).

Second, suppose that x and y belong to different cosets. Thus we may assume that x belongs to a + J(R) which has colour α and y belongs to b + J(R) which has colour β. Since x is adjacent to y in G(R), we may easily conclude that a + J(R) is adjacent to b + J(R) in G(R/J(R)). This implies that α ≠ β. We may write x = a + r_{i} and y = b + r_{j}. Therefore x has either colour α or (α, r_{i}), while y has either colour β or (β, r_{j}), and so, in this case, x and y have different colours.

Thus x and y have different colours, and so we have a colouring of the vertices of G(R). By counting the number of colours used, we conclude that G(R) admits a (|J(R)|k + ℓ)-colouring as requested. □

Lemma 3.3. Let R be a ring and suppose that 2 + J(R) ∉ U(R/J(R)), where J(R) denotes the Jacobson radical of R. Also let k be a positive integer. Then the following statements hold:

(a) If the unit graph G(R/J(R)) has a clique of size k, then the unit graph G(R) also has a clique of size k.

(b) If the unit graph G(R/J(R)) admits a k-colouring, then the unit graph G(R) also admits a k-colouring.

Proof. Since 2 + J(R) ∉ U(R/J(R)), it is easy to see that for every x ∈ R, we have 2x ∉ U(R), and thus, by part (c) of Proposition 3.1, x + J(R) is a coclique in G(R).

Now for the proof of part (a), suppose that S = {x_{1} + J(R), …, x_{k} + J(R)} is a clique in G(R/J(R)). By part (a) of Proposition 3.1, for every 1 ≤ i, j ≤ k with i ≠ j, every element of x_{i} + J(R) is adjacent to every element of x_{j} + J(R) in G(R). Thus we conclude that the set {x_{1}, …, x_{k}} is a clique in G(R) of size k. Therefore, the requested clique in G(R) exists.

For the proof of part (b), partition the elements of R into distinct cosets of R/J(R), and then colour the elements of a given coset with the colour of that coset. It is easy to see that G(R) now admits a k-colouring. □

We now recall some definitions and notations concerning graphs for later use. A complete graph is a graph in which each pair of distinct vertices is joined by an edge. We denote the complete graph with n vertices by K_{n}.

For a graph G, let V (G) denote the set of vertices and let E(G) denote the set of edges. Let G_{1} and G_{2} be two graphs. The join of G_{1} and G_{2}, which is denoted by G_{1} ∨G_{2}, is a graph with vertex set V (G_{1})∪V (G_{2}) and edge set E(G_{1})∪E(G_{2})∪{xy | x ∈ V (G_{1}), y ∈ V (G_{2})}.

For a graph G and a vertex x ∈ V (G), the degree of x is the number of edges of G incident with x. For every non-negative integer r, the graph G is called r-regular if the degree of each vertex of G is equal to r. A subgraph H of a graph G is called a spanning subgraph if V (H) = V (G). A 1-regular spanning subgraph H of G is called a perfect matching of G. We recall that if we omit a perfect matching from a complete graph K_{2n}, then the resulting graph is called a cocktail party and denoted by CP(2n).

We state the following result, which gives us some information on the structure of the unit graphs of fields.

Proposition 3.4 ([1], Theorem 3.8). Let R be a ring, n be a positive integer and p be an odd prime. Then G(R) ≅ K_{1} ∨ CP(p^{n} − 1) if and only if R is a field with p^{n} elements.

We now state the following lemma.

Lemma 3.5. Let F_{i}, 1 ≤ i ≤ n, be a field with characteristic not equal to 2. Then the following statements hold:

(a) The unit graph G(∏_{i=1}^{n} F_{i}) has a clique of size \frac{1}{2^{n}} ∏_{i=1}^{n}(|F_{i}|−1)+n with exactly n non-unit elements.

(b) The unit graph G(∏_{i=1}^{n} F_{i}) admits a (\frac{1}{2^{n}} ∏_{i=1}^{n}(|F_{i}| − 1) + n)-colouring, among which exactly n colours are used to colour non-unit elements.

Proof. For the proof of part (a), suppose that for every i with 1 ≤ i ≤ n, the set S_{i} is a maximum clique in the unit graph G(F_{i}) and choose a_{i} as a non-zero element of S_{i}. Then it is easy to see that the set

S = ( ∏_{i=1}^{n}(S_{i} \ {0})) ∪ {(a_{1}, …, a_{i−1}, 0, a_{i+1}, …, a_{n}) | 1 ≤ i ≤ n}

is a clique in the unit graph G(∏_{i=1}^{n} F_{i}) with exactly n non-unit elements. For every i with 1 ≤ i ≤ n, by Proposition 3.4, we conclude that G(F_{i}) ≅ K_{1} ∨ CP(|F_{i}| − 1). Therefore we have ω(G(F_{i})) = 1 + (|F_{i}| − 1)/2. Also we have 0 ∈ S_{i} and, thus, |S_{i} \ {0}| = |S_{i}| − 1. Therefore, we obtain that |S| = ∏_{i=1}^{n}(|S_{i}| − 1) + n = ∏_{i=1}^{n}(ω(G(F_{i})) − 1) + n = \frac{1}{2^{n}} ∏_{i=1}^{n}(|F_{i}| − 1) + n. And therefore, the requested clique in G(∏_{i=1}^{n} F_{i}) exists.

For the proof of part (b), for every i with 1 ≤ i ≤ n, we may assume that

F_{i} = {0, α_{1}^{i}, …, α_{(|F_{i}|−1)/2}^{i}, −α_{1}^{i}, …, −α_{(|F_{i}|−1)/2}^{i}}.

Suppose that 1 ≤ k_{i} ≤ (|F_{i}| − 1)/2, 1 ≤ i ≤ n, and consider T_{k_{1},...,k_{n}} = ∏_{i=1}^{n} T_{k_{i}}^{i}, where T_{k_{i}}^{i} = {α_{k_{i}}^{i}, −α_{k_{i}}^{i}}. It is easy to see that T_{k_{1},...,k_{n}}, where 1 ≤ k_{i} ≤ (|F_{i}| − 1)/2, 1 ≤ i ≤ n, is a coclique in G(∏_{i=1}^{n} F_{i}). Note that every element of ∏_{i=1}^{n} F_{i} either belongs to T_{k_{1},...,k_{n}} for some 1 ≤ k_{i} ≤ (|F_{i}|−1)/2, 1 ≤ i ≤ n, or has a coordinate equal to zero. Now suppose that x is a given vertex of G(∏_{i=1}^{n} F_{i}). If x belongs to T_{k_{1},...,k_{n}} for some 1 ≤ k_{i} ≤ (|F_{i}| − 1)/2, 1 ≤ i ≤ n, then we colour x by colour (k_{1}, …, k_{n}). In the other case, we colour x by colour i, where the ith coordinate is the first zero coordinate of x. Clearly this is a colouring of G(∏_{i=1}^{n} F_{i}). By counting the number of colours used, we conclude that G(∏_{i=1}^{n} F_{i}) admits a (\frac{1}{2^{n}} ∏_{i=1}^{n}(|F_{i}| − 1) + n)-colouring. Here, exactly n colours are used to colour non-unit elements, as requested. □

The following result characterizes the unit graphs of rings that are complete graphs.

Proposition 3.6 ([1], Theorem 3.4). Let R be a ring. Then the unit graph G(R) is a complete graph if and only if R is a field with characteristic equal to 2.

We also need the following result later.

Lemma 3.7. Let F_{i}, 1 ≤ i ≤ n, be a field such that F_{1}, …, F_{ℓ} all have characteristic equal to 2 with |F_{1}| ≤ … ≤ |F_{ℓ}| and F_{ℓ+1}, …, F_{n} all have characteristic not equal to 2. Then the following statements hold:

(a) The unit graph G(∏_{i=1}^{n} F_{i}) has a clique of size |F_{1}|.

(b) The unit graph G(∏_{i=1}^{n} F_{i}) admits a |F_{1}|-colouring.

Proof. For the proof of part (a), for every i with 2 ≤ i ≤ ℓ, assume that S_{i} is a subset of F_{i} with |S_{i}| = |F_{1}| and consider f_{i} : F_{1} ⟶ S_{i} as a bijection. Since by Proposition 3.6, the unit graph G(F_{i}), 1 ≤ i ≤ ℓ, is a complete graph,

S = {(α, f_{2}(α), …, f_{ℓ}(α), 1, …, 1) | α ∈ F_{1}}

is a clique in G(∏_{i=1}^{n} F_{i}). It is clear that the size of this clique is equal to |F_{1}|. Therefore the requested clique in G(∏_{i=1}^{n} F_{i}) exists.

For the proof of part (b), for every α ∈ F_{1}, we consider T_{α} = {α} × ∏_{i=2}^{n} F_{i}. Note that every element of ∏_{i=1}^{n} F_{i} belongs to T_{α} for some α ∈ F_{1}. Now suppose that x is a given vertex of G(∏_{i=1}^{n} F_{i}). If x belongs to T_{α} for some α ∈ F_{1}, then we colour x by colour α. Clearly this is a colouring of G(∏_{i=1}^{n} F_{i}). By counting the number of colours used, we conclude that G(∏_{i=1}^{n} F_{i}) admits a |F_{1}|-colouring. □

We are now ready to prove the main result of this paper. But before starting the proof, it may be helpful to highlight the following.

Remark 3.8. It is known that every ring is isomorphic to a direct product of local rings (see [4, Page 95]). Thus for a given ring R, we may write R ≅ ∏_{i=1}^{n} R_{i}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. It is easy to see that

{R_{1} × … × R_{i−1} × 𝔪_{i} × R_{i+1} × … × R_{n} | 1 ≤ i ≤ n}

is the set of all maximal ideals of ∏_{i=1}^{n} R_{i}, and thus we conclude that the Jacobson radical of R is isomorphic to J(∏_{i=1}^{n} R_{i}) = ∏_{i=1}^{n} 𝔪_{i}. Also note that the function f : ∏_{i=1}^{n} R_{i} ⟶ ∏_{i=1}^{n} R_{i}/𝔪_{i}, given by f(r_{1}, …, r_{n}) = (r_{1} + 𝔪_{1}, …, r_{n} + 𝔪_{n}), is an epimorphism with ker f = ∏_{i=1}^{n} 𝔪_{i}, and thus we have R/J(R) ≅ ∏_{i=1}^{n} R_{i}/ ∏_{i=1}^{n} 𝔪_{i} ≅ ∏_{i=1}^{n} R_{i}/𝔪_{i}. Finally, in the proof of Theorem 2.2, we will use the quantity

\frac{|J(R)|}{2^{n}} ∏_{i=1}^{n}(|R_{i}/𝔪_{i}| − 1) + n.

Since |J(R)| = ∏_{i=1}^{n} |𝔪_{i}|, this quantity has now the following simpler form:

\frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n.

Proof of Theorem 2.2. We may write R ≅ ∏_{i=1}^{n} R_{i}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. Therefore, R/J(R) ≅ ∏_{i=1}^{n} F_{i}, where for every i with 1 ≤ i ≤ n, F_{i} = R_{i}/𝔪_{i} is a field and J(R), of course, denotes the Jacobson radical of R (see Remark 3.8). There are two possibilities: either all of the F_{i}’s have characteristic not equal to 2 or at least one of the F_{i}’s has characteristic equal to 2.

(1) Suppose that all of the F_{i}’s have characteristic not equal to 2. Therefore, we have (2, …, 2) ∈ U(∏_{i=1}^{n} F_{i}) and, thus, 2 + J(R) ∈ U(R/J(R)).

By part (a) of Lemma 3.5, G(∏_{i=1}^{n} F_{i}), and therefore, G(R/J(R)) has a clique of size \frac{1}{2^{n}} ∏_{i=1}^{n}(|F_{i}|−1)+n with exactly n non-unit elements. Thus, by part (a) of Lemma 3.2 and Remark 3.8, we conclude that G(R) has a clique of size \frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n. This implies that ω(G(R)) ≥ \frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n.

By part (b) of Lemma 3.5, G(∏_{i=1}^{n} F_{i}), and therefore, G(R/J(R)) admits a (\frac{1}{2^{n}} ∏_{i=1}^{n}(|F_{i}| − 1) + n)-colouring, among which exactly n colours are used to colour nonunit elements. Thus, by part (b) of Lemma 3.2 and Remark 3.8, we conclude that G(R) admits a (\frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n)-colouring. This implies that χ(G(R)) ≤ \frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n.

Therefore, since χ(G(R)) ≥ ω(G(R)), we conclude that

χ(G(R)) = ω(G(R)) = \frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n,

which implies that the unit graph G(R) is weakly perfect.

(2) Suppose that at least one of the F_{i}’s has characteristic equal to 2. Therefore, we have (2, …, 2) ∉ U(∏_{i=1}^{n} F_{i}) and, thus, 2 + J(R) ∉ U(R/J(R)).

By reordering we may assume that F_{1}, …, F_{ℓ} all have characteristic equal to 2 with |F_{1}| ≤ … ≤ |F_{ℓ}| and F_{ℓ+1}, …, F_{n} all have characteristic not equal to 2.

By part (a) of Lemma 3.7, G(∏_{i=1}^{n} F_{i}), and therefore, G(R/J(R)) has a clique of size |R_{1}|/|𝔪_{1}|. Thus, by part (a) of Lemma 3.3, we conclude that G(R) has a clique of size |R_{1}|/|𝔪_{1}|. This implies that ω(G(R)) ≥ |R_{1}|/|𝔪_{1}|.

By part (b) of Lemma 3.7, G(∏_{i=1}^{n} F_{i}), and therefore, G(R/J(R)) admits a ( |R_{1}|/|𝔪_{1}|)-colouring. Thus, by part (b) of Lemma 3.3, we conclude that G(R) admits a (|R_{1}|/|𝔪_{1}|)-colouring. This implies that χ(G(R)) ≤ |R_{1}|/|𝔪_{1}|.

Therefore, since χ(G(R)) ≥ ω(G(R)), we conclude that

χ(G(R)) = ω(G(R)) = |R_{1}|/|𝔪_{1}|,

which implies that the unit graph G(R) is weakly perfect. □

Let us note that the proof of Theorem 2.2 gives us an explicit formula for the chromatic number of G(R). For a given ring R, we may write R ≅ R_{1} × … × R_{n}, where every R_{i} is a local ring with maximal ideal 𝔪_{i}. If 2 ∉ U(R), by reordering, we may assume that R_{1}, …, R_{ℓ} all have characteristic equal to 2 with |R_{1}|/|𝔪_{1}| ≤ … ≤ |R_{ℓ}|/|𝔪_{ℓ}| and R_{ℓ+1}, …, R_{n} all have characteristic not equal to 2. Then

χ(G(R)) = \{ \begin{matrix}\frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − |𝔪_{i}|) + n, & if 2 ∈ U(R), \\ |R_{1}|/|𝔪_{1}|, & if 2 ∉ U(R). \end{matrix}

Note that this formula reduced to the simpler form if all of the R_{i}’s are fields.

χ(G(R)) = \{ \begin{matrix}\frac{1}{2^{n}} ∏_{i=1}^{n}(|R_{i}| − 1) + n, & if 2 ∈ U(R), \\ |R_{1}|, & if 2 ∉ U(R). \end{matrix}

We conclude this paper with two examples which illustrate the main result and the above formulas.

Example 3.9. Let k > 1 be an integer and write k = p_{1}^{r_{1}} … p_{n}^{r_{n}}, where the p_{i}’s are distinct prime numbers and the r_{i}’s are positive integers. Therefore, we obtain ℤ_{k} ≅ ℤ_{p_{1}^{r_{1}}} × … × ℤ_{p_{n}^{rn}}, and so we have the following formula, where φ denotes the Euler phi function:

χ(G(ℤ_{k})) = \{ \begin{matrix}\frac{1}{2^{n}} φ(k) + n, & if k is odd, \\ 2, & if k is even. \end{matrix}

Therefore, for example, the chromatic number of G(ℤ_{9}) is equal to four and the chromatic number of G(ℤ_{12}) is equal to two. In Figure 3, we illustrate these points. Here the different bullets indicate the presence of the different colours.

[figure: 1; 4; 7; 0; 2; 5; 8; 3; 6; 0; 2; 4; 6; 8; 10; 1; 3; 5; 7; 9; 11]

Figure 3. The unit graphs G(ℤ_{9}) and G(ℤ_{12}) and their 4-colouring and 2-colouring.

Example 3.10. The chromatic number of G(ℤ_{3}[x]/⟨x^{2}⟩) is equal to four. In Figure 4, we illustrate this point. Here the different bullets indicate the presence of the different colours.

[figure: 1; 1+α; 1+2α; 2α; 2; 2+2α; 2+α; 0; α]

Figure 4. The unit graph G(ℤ_{3}[x]/⟨x^{2}⟩) and its 4-colouring.

Acknowledgment

The authors would like to thank the referee for his/her interest in the subject and for carefully reading the paper.

References

[1] N. Ashrafi, H. R. Maimani, M. R. Pournaki, S. Yassemi, Unit graphs associated with rings, Comm. Algebra, to appear.

[2] M. F. Atiyah, I. G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont. 1969.

[3] R. P. Grimaldi, Graphs from rings, Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congr. Numer. 71 (1990), 95–103.

[4] B. R. McDonald, Finite Rings with Identity, Pure and Applied Mathematics, vol. 28, Marcel Dekker, Inc., New York, 1974.

[5] D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

H. R. Maimani, Mathematics Section, Department of Basic Sciences, Shahid Rajaee Teacher Training University, P.O. Box 16785-163, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: maimani@ipm.ir

M. R. Pournaki, Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11155-9415, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: pournaki@ipm.ir
URL: http://math.ipm.ac.ir/pournaki/

S. Yassemi, School of Mathematics, Statistics and Computer Science, College of Science, University of Tehran, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

E-mail address: yassemi@ipm.ir
URL: http://math.ipm.ac.ir/yassemi/