A CLASS OF WEAKLY PERFECT GRAPHS

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 note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.

1. Introduction

Throughout the note by a graph G we mean a finite undirected graph without loops or multiple edges. For undefined terms and concepts the reader is referred to [4]. A k-coloring of the vertices of G is an assignment of k colors to the vertices of G in such a way that no two adjacent vertices receive the same color. The chromatic number of G, denoted by χ(G), is the smallest number k such that G admits a k-coloring. A survey of the most famous graph coloring methods can be found in [2]. 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) has been extensively studied by many authors. Nevertheless, finding the chromatic number and the clique number of a graph is long known to be an NP-hard problem (see [1]).

It is easy to see that χ(G) ≥ ω(G), because every vertex of a clique should get a different color. 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 5. 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). It is known that deciding whether χ(G) = ω(G) is an NP-complete problem (see [3]).

In this note a new class of weakly perfect graphs are presented. Moreover, we give an explicit formula for the chromatic number of such graphs. The procedure of the proof of our main result may lead to an algorithm for coloring of such graphs.

2. Main result

Let p be a prime number and let k be a positive integer. We define a graph, denoted by G(p^{k}), based on numbers and their sums. The vertices of G(p^{k}) are the elements of [p^{k}] = {1, …, p^{k}} and distinct vertices x and y are defined to be adjacent if and only if gcd(x + y, p) = 1.

2000 Mathematics Subject Classification. Primary: 05C69, 05C17; Secondary: 11A25.

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

The research of H. R. Maimani and M. R. Pournaki was in part supported by a grant from IPM (No. 88050214 and No. 88130113). The research of S. Yassemi was in part supported by a grant from the University of Tehran.

The graphs G(3) and G(4) demonstrate in Figure 1. Also the graph G(9), as illustrated in Figure 2, shows that when the number of vertices is large, it is not so easy to find the chromatic number of the graph G(p^{k}). The main result of this note provides that all graphs G(p^{k}) are weakly perfect and gives an explicit formula for the chromatic number of such graphs.

[figure: 3; 1; 2; 1; 2; 3; 4]

Figure 1. The graphs G(3) and G(4)

Theorem 2.1. Let p be a prime number and let k be a positive integer. Then the graph G(p^{k}) is a weakly perfect graph. Moreover, we have

χ(G(p^{k})) = ω(G(p^{k})) = \{ \begin{matrix}2 & if p = 2, \\ p^{k−1}(p − 1)/2 + 1 & if p > 2. \end{matrix}

In order to prove Theorem 2.1, we start with a couple of lemmas.

Lemma 2.2. Let p > 2 be a prime number and let k be a positive integer. If H = {ip | 1 ≤ i ≤ p^{k−1}}, then there exists a maximum clique C in G(p^{k}) such that C∩H = {p^{k}}.

Proof. Since the sum of every two elements of H is a multiple of p, H is a set of pairwise nonadjacent vertices. Thus for every clique B in the graph G(p^{k}) we have |B ∩ H| ≤ 1.

We claim that for every maximum clique B̂ in G(p^{k}) we have |B̂ ∩ H| = 1. In order to prove the claim, by contrary, suppose that there exists a maximum clique B̂ in G(p^{k}) such that B̂ ∩ H = ∅. Let i with 1 ≤ i ≤ p^{k−1} be given. For every x ∈ B̂ we have gcd(x, p) = 1 and so we obtain that gcd(x + ip, p) = 1. Thus x is adjacent to ip. Therefore every element of B̂ is adjacent to ip and so B̂ ∪ {ip} is a clique in G(p^{k}). But this is a contradiction with our choice of B̂ as a maximum clique. Therefore the claim holds.

Now choose B̂ as a maximum clique in G(p^{k}) with |B̂ ∩ H| = 1. Suppose that B̂ ∩ H = {ℓp}, for some ℓ with 1 ≤ ℓ ≤ p^{k−1}. If we consider C = (B̂ \ {ℓp}) ∪ {p^{k}}, then C is a maximum clique in G(p^{k}) such that C ∩ H = {p^{k}}. □

Lemma 2.3. Let p > 2 be a prime number and let k be a positive integer. Then we have ω(G(p^{k})) = p^{k−1}(p − 1)/2 + 1.

Proof. Let B_{i} = {(i − 1)p + 1, …, (i − 1)p + (p − 1)/2}, 1 ≤ i ≤ p^{k−1}. We claim that B = B_{1} ∪ … ∪ B_{p^{k−1}} ∪ {p^{k}} is a clique in G(p^{k}). In order to show this, let x ∈ B_{i} and y ∈ B_{j} be two distinct vertices, 1 ≤ i, j ≤ p^{k−1}. We may write x = (i − 1)p + s and y = (j − 1)p + t, where 1 ≤ s, t ≤ (p − 1)/2, and so we conclude that x + y = (i+j −2)p+s+t. Since 2 ≤ s+t ≤ p−1, gcd(s+t, p) = 1 and thus gcd(x+y, p) = 1. Therefore x and y are adjacent. On the other hand, gcd(x + p^{k}, p) = 1 and so p^{k} is adjacent to x. Therefore every two distinct vertices of B are adjacent and so the claim holds. It is obvious that B has size p^{k−1}(p − 1)/2 + 1.

Now suppose that C is a maximum clique in G(p^{k}) with size larger than p^{k−1} × (p − 1)/2 + 1. By Lemma 2.2, we may assume that p^{k} ∈ C. We may partition the set [p^{k}] into the sets A_{1}, …, A_{p^{k−1}}, where for every i with 1 ≤ i ≤ p^{k−1}, A_{i} = {(i − 1)p + 1, …, ip}. Suppose that for every ℓ with 1 ≤ ℓ ≤ p^{k−1} − 1 we have |A_{ℓ} ∩ C| ≤ (p − 1)/2 as well as we have |A_{p^{k−1}} ∩ C| ≤ (p − 1)/2 + 1. Then we obtain that

|C| = |(A_{1} ∩ C) ∪ … ∪ (A_{p^{k−1}−1} ∩ C) ∪ (A_{p^{k−1}} ∩ C)|
= |A_{1} ∩ C| + … + |A_{p^{k−1}−1} ∩ C| + |A_{p^{k−1}} ∩ C|
≤ (p^{k−1} − 1)(p − 1)/2 + (p − 1)/2 + 1
= p^{k−1}(p − 1)/2 + 1.

This is a contradiction with our choice of C and, therefore, either there exists ℓ with 1 ≤ ℓ ≤ p^{k−1} − 1 such that |A_{ℓ} ∩ C| > (p − 1)/2 or |A_{p^{k−1}} ∩ C| > (p − 1)/2 + 1.

Suppose that there exists ℓ with 1 ≤ ℓ ≤ p^{k−1} − 1 such that |A_{ℓ} ∩ C| > (p − 1)/2. We now consider Â_{i} = {(ℓ − 1)p + i, (ℓ − 1)p + (p − i)}, 1 ≤ i ≤ (p − 1)/2. One may easily see that A_{ℓ} can be partitioned into disjoint subsets Â_{1},…,Â_{(p−1)/2} and {ℓp}. Since p^{k} ∈ C and p^{k} is not adjacent to ℓp, we obtain that ℓp is not in C. Therefore

|(Â_{1} ∩ C) ∪ … ∪ (Â_{(p−1)/2} ∩ C)| > (p − 1)/2

and so we obtain that

|Â_{1} ∩ C| + … + |Â_{(p−1)/2} ∩ C| > (p − 1)/2.

Thus there exists i with 1 ≤ i ≤ (p − 1)/2 such that |Â_{i} ∩ C| ≥ 2. In other words, C has at least two elements contained in A_{i}, for some i with 1 ≤ i ≤ (p−1)/2. Therefore there exist x, y ∈ C such that x = (ℓ − 1)p + i and y = (ℓ − 1)p + (p − i). Since x + y = (2ℓ − 1)p, x is not adjacent to y. But this is a contradiction with our choice of C as a clique. By a similar argument the case |A_{p^{k−1}} ∩ C| > (p − 1)/2 + 1 also leads to a contradiction. Thus there is no maximum clique in G(p^{k}) with size larger than p^{k−1}(p − 1)/2 + 1.

Therefore B is a maximum clique in G(p^{k}) and so we conclude that ω(G(p^{k})) = p^{k−1}(p − 1)/2 + 1. □

Proof of Theorem 2.1. First, suppose that p = 2. Let X be the set of odd numbers in [2^{k}] and Y be the set of even numbers in [2^{k}]. Therefore X and Y partition the vertex set of G(2^{k}) into two subsets. It is clear that no pair of distinct elements of X or Y are adjacent. Therefore G(2^{k}) is a bipartite graph and so χ(G(2^{k})) = ω(G(2^{k})) = 2.

Second, suppose that p > 2. Consider H = {ip | 1 ≤ i ≤ p^{k−1}}. Therefore, by Lemma 2.2, there exists a maximum clique C in G(p^{k}) such that C ∩ H = {p^{k}}. We may partition the set [p^{k}] into the sets H_{i}^{j} = {(i − 1)p + j, ip − j}, 1 ≤ i ≤ p^{k−1}, 1 ≤ j ≤ (p − 1)/2, and H. One may easily show that the sets H_{i}^{j}, 1 ≤ i ≤ p^{k−1}, 1 ≤ j ≤ (p−1)/2, and H are sets of pairwise nonadjacent vertices. Now color all of the vertices in the set H_{i}^{j} by the color (i, j) and also color the vertices of H by the color p. Therefore we have a (p^{k−1}(p−1)/2+1)-coloring of G(p^{k}), since the number of the sets H_{i}^{j} are equal to p^{k−1}(p − 1)/2. Therefore χ(G(p^{k})) ≤ p^{k−1}(p − 1)/2 + 1. Thus Lemma 2.3 implies that χ(G(p^{k})) ≤ ω(G(p^{k})). On the other hand, χ(G(p^{k})) ≥ ω(G(p^{k})). Therefore we obtain that

χ(G(p^{k})) = ω(G(p^{k})) = p^{k−1}(p − 1)/2 + 1,

as requested. □

Theorem 2.1 shows that the chromatic number of the graph G(9) is equal to four. In Figure 2 we illustrate this point. Here the different bullets indicate the presence of the different colors.

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

Figure 2. The graph G(9) and its 4-coloring

References

[1] M. R. Garey, D. S. Johnson, Computers and Intractabilitiy: A Guide to the Theory of NP-Completeness, W. H. Freman and Company, New York, 1979.

[2] M. Kubale, Graph Colorings, American Mathematical Society, 2004.

[3] C. McDiarmid, B. Reed, Channel assignment and weighted colouring, Networks 36 (2000), 114–117.

[4] 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, 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.

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