Chromatic and clique numbers of a class of perfect graphs

Abstract

Let p be a prime number and n be a positive integer. The graph G p (n) is a graph with vertex set [n]=1,2,ldots,n , in which there is an arc from u to v if and only if uneqv and pnmidu+v . In this paper it is shown that G p (n) is a perfect graph. In addition, an explicit formula for the chromatic number of such graph is given.

Keywords

• perfect graph
• clique number
• chromatic number