Case 2
$n\ne {p}_{1}^{2}$. 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 ${p}_{m}^{{a}_{m}}$ does not divide v. Take the positive integer s ≤ a_{m} such that ${p}_{m}^{s-1}$ divides v but ${p}_{m}^{s}$ does not divide v. Then $v((\sqrt{n}/{p}_{m}^{s})\sqrt{n})$ is not a multiple of n; so v and $(\sqrt{n}/{p}_{m}^{s})\sqrt{n}$ are not adjacent. We color v with $\sqrt{n}/{p}_{m}^{s}$
Now, it remains to check that any two vertices with the same color cannot be adjacent. Let v_{1} and v_{2} be distinct elements of Z(ℤ_{n}) which have the same color. Since C is a clique, v_{1} and v_{2} cannot both belong to C. Suppose that v_{1} ∈ C and v_{2} ∈ Z(ℤ_{n}) C. Let $\widehat{\sqrt{n}/{p}_{m}^{s}}$ be the color of v_{2} for some m ∈ {1, …, r} and s ∈ {1, …, a_{m}}. Then v_{2} is not divisible by ${p}_{m}^{s}$ by the coloring of v_{2}. Since v_{1} ∈ C, ${v}_{1}=(\sqrt{n}/{p}_{m}^{s})\sqrt{n}$. Therefore ${p}_{m}^{2{a}_{m}}$ does not divide v_{1}v_{2}. Hence v_{1} is not adjacent to v_{2}. Suppose that v_{1}, v_{2} ∈ Z(ℤ_{n}) C, and let $\widehat{\sqrt{n}/{p}_{m}^{s}}$ be the color of v_{1} and v_{2} for some m ∈ {1, …, r} and s ∈ {1, …, a_{m}}. Then by the coloring of v_{1} and v_{2}, ${p}_{m}^{s}$ divides neither v_{1} nor v_{2}; so ${p}_{m}^{2s}$ does not divide v_{1}v_{2}. Since s ≤ a_{m}, ${p}_{m}^{2{a}_{m}}$ does not divide v_{1}v_{2}. Hence v_{1}v_{2} is not a multiple of n, which means that v_{1} and v_{2} are not adjacent.
In either case, Γ(ℤ_{n}) is ($(\sqrt{n}-1)-\text{colorable}$. Note that by Lemma 3.4, $\chi (\mathrm{\Gamma}({\mathbb{Z}}_{n}))\ge \sqrt{n}-1$. Thus $\chi (\mathrm{\Gamma}({\mathbb{Z}}_{n}))=\sqrt{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 v ∈ R. Then v is not divisible by 3; so we color v with 2̂. Let B = {3, 9, 15, 21, 27, 33} and let v ∈ B. 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 p_{1}, … , p_{r}, q_{1}, … , q_{s} be distinct primes, a_{1}, … , a_{r}, b_{1}, … , b_{s} nonnegative integers, not all zero, and let $n={p}_{1}^{2{a}_{1}}\cdots {p}_{r}^{2{a}_{r}}{q}_{1}^{2{b}_{1}+1}\cdots {q}_{s}^{2{b}_{s}+1}$. If${C}_{1}=\{k{p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}+1}\cdots {q}_{s}^{{b}_{s}+1}\mid k=1,\dots ,{p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}}\cdots {q}_{s}^{{b}_{s}}-1\}$and${C}_{2}=\{{p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}+1}\cdots {q}_{s}^{{b}_{s}+1}/{q}_{i}\mid i=1,\dots ,s\}$, then C_{1} ∪ C_{2}is a maximal clique of Γ(ℤ_{n}).
Proof
We first note that C_{1} ∩ C_{2} = ∅︀. Let C = C_{1} ∪ C_{2}. 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 c ∈ C. Therefore m is a multiple of ${p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}}\cdots {q}_{i-1}^{{b}_{i-1}}{q}_{i}^{{b}_{i}+1}{q}_{i+1}^{{b}_{i+1}}\cdots {q}_{s}^{{b}_{s}}$ for all i = 1, …, s. Hence m is a multiple of ${p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}+1}\cdots {q}_{s}^{{b}_{s}+1}$, which implies that m ∈ C_{1}. This contradicts the choice of m. Thus C is a maximal clique of Γ(ℤ_{n}).
Theorem 3.8
Let p_{1}, …, p_{r}, q_{1}, …, q_{s} be distinct primes and a_{1}, …, a_{r}, b_{1}, …, b_{s} nonnegative integers, not all zero. If$n={p}_{1}^{2{a}_{1}}\cdots {p}_{r}^{2{a}_{r}}{q}_{1}^{2{b}_{1}+1}\cdots {q}_{s}^{2{b}_{s}+1}$, then$\chi (\mathrm{\Gamma}({\mathbb{Z}}_{n}))={p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}}\cdots {q}_{s}^{{b}_{s}}-1+s$.
Proof
Let $x={p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}}\cdots {q}_{s}^{{b}_{s}}$ and $y={p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}+1}\cdots {q}_{s}^{{b}_{s}+1}$. Then n = xy. Let C_{1} = {ky | k = 1, …, x−1}, C_{2} = {y/q_{i} | i = 1, …, s}, and C = C_{1} ∪ C_{2}. Then by Lemma 3.7, C is a maximal clique of Γ(ℤ_{n}). For each k = 1, …, x − 1, let k̂ be the color of ky and for each i = 1, …, s, let ī be the color of y/q_{i}. Note that by Theorem 2.1, Γ(ℤ_{n}) is not a complete graph. Let v ∈ Z(ℤ_{n}) C.
Case 1
There exists an element c ∈ C_{1} which is not adjacent to v. In this case, v is not divisible by x. If ${q}_{1}^{{b}_{1}}\cdots {q}_{s}^{{b}_{s}}$ divides v, then ${p}_{m}^{{a}_{m}}$ does not divide v for some m ∈ {1, …, r}; so we can take the positive integer α ≤ a_{m} such that ${p}_{m}^{\alpha -1}$ divides v but ${p}_{m}^{\alpha}$ does not divide v. Hence v is not adjacent to $(x/{p}_{m}^{\alpha})y$. We color v with $\widehat{x/{p}_{m}^{\alpha}}$. If ${q}_{t}^{{b}_{t}}$ does not divide v for some t ∈ {1, …, s}, then we can find the positive integer β ≤ b_{t} such that ${q}_{t}^{\beta -1}$ divides v but ${q}_{t}^{\beta}$ does not divide v. Hence v is not adjacent to $(x/{q}_{t}^{\beta})y$. We color v with $\widehat{x/{q}_{t}^{\beta}}$.
Case 2
v is adjacent to c for all c ∈ C_{1}. In this case, v is a multiple of x. If ${q}_{1}^{{b}_{1}+1}\cdots {q}_{s}^{{b}_{s}+1}$ divides v, then v ∈ C_{1}, which is a contradiction to the choice of v. Therefore we can find an element i ∈ {1, …, s} such that ${q}_{i}^{{b}_{i}}$ divides v but ${q}_{i}^{{b}_{i}+1}$ does not divide v. Clearly, v(y/q_{i}) is not a multiple of n. Hence v and y/q_{i} are not adjacent. We color v with ī.
It remains to show that there are no adjacent vertices with the same color. Let v_{1}, v_{2} ∈ Z(ℤ_{n}) have the same color. Since C is a clique, at least one of v_{1} and v_{2} does not belong to C. Suppose that v_{1} ∈ C but v_{2} ∈ Z(ℤ_{n}) C. If the color of v_{1} and v_{2} is $\widehat{x/{p}_{m}^{\alpha}}$ for some m ∈ {1, …, r} and α ∈ {1, …, a_{m}}, then by the coloring of v_{1} and v_{2}, ${v}_{1}=(x/{p}_{m}^{\alpha})y$ and ${p}_{m}^{\alpha}$ does not divide v_{2}; so v_{1}v_{2} is not a multiple of n. Hence v_{1} is not adjacent to v_{2}. If the color of v_{1} and v_{2} is $\widehat{x/{q}_{t}^{\beta}}$ for some t ∈ {1, …, s} and β ∈ {1, …, b_{t}}, then by the coloring of v_{1} and v_{2}, ${v}_{1}=(x/{q}_{t}^{\beta})y$ and ${q}_{t}^{\beta}$ does not divide v_{2}; so v_{1}v_{2} is not a multiple of n. Hence v_{1} is not adjacent to v_{2}. If ī is the color of v_{1} and v_{2} for some i ∈ {1, …, s}, then v_{1} = y/q_{i} and so by the coloring of v_{2}, v_{1} and v_{2} are not adjacent. We next suppose that v_{1}, v_{2} ∈ Z(ℤ_{n}) C. If $\widehat{x/{p}_{m}^{\alpha}}$ is the color of v_{1} and v_{2} for some m ∈ {1, …, r} and α ∈ {1, …, a_{m}}, then by Case 1, ${p}_{m}^{\alpha}$ divides neither v_{1} nor v_{2}; so ${p}_{m}^{2{a}_{m}}$ does not divide v_{1}v_{2}. Hence v_{1} and v_{2} are not adjacent. If $\widehat{x/{q}_{t}^{\beta}}$ is the color of v_{1} and v_{2} for some t ∈ {1, …, s} and β ∈ {1, …, b_{t}}, then by Case 1, ${q}_{t}^{\beta}$ divides neither v_{1} nor v_{2}; so ${q}_{t}^{2{b}_{t}}$ does not divide v_{1}v_{2}. Hence v_{1} and v_{2} are not adjacent. If ī is the color of v_{1} and v_{2} for some i ∈ {1, …, s}, then by Case 2, ${q}_{i}^{{b}_{i}+1}$ divides neither v_{1} nor v_{2}. Hence ${q}_{i}^{2{b}_{i}+1}$ cannot divide v_{1}v_{2}, which means that v_{1} and v_{2} are not adjacent. Consequently, Γ(ℤ_{n}) is ($({p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}}\cdots {q}_{s}^{{b}_{s}}-1+s)-\text{colorable}$. Note that by Lemma 3.7, $\chi (\mathrm{\Gamma}({\mathbb{Z}}_{n}))\ge {p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}}\cdots {q}_{s}^{{b}_{s}}-1+s$. Thus $\chi (\mathrm{\Gamma}({\mathbb{Z}}_{n}))={p}_{1}^{{a}_{1}}\cdots {p}_{r}^{{a}_{r}}{q}_{1}^{{b}_{1}}\cdots {q}_{s}^{{b}_{s}}-1+s$.
Example 3.9
Consider Γ(ℤ_{18}). Let C_{1} = {6, 12} and C_{2} = {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 v ∈ R. 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 v ∈ B. Then v is adjacent to all elements in C_{1}. 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 C_{1} = {12, 24, 36, 48, 60} and C_{2} = {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 v ∈ P. 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 v ∈ B. 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 v ∈ Y. Then v is adjacent to all elements in C_{1}. 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.