Chromatic and clique numbers of a class of perfect graphs

Document Type : Research Paper


Azad University, Chaluse Branch


‎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 $u\neq v$ and‎ ‎$p\nmid u+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‎.


Main Subjects

R. ‎Diestel (2010). Graph theory. ‎Fourth edition‎, ‎Graduate Texts in Mathematics‎, ‎‎Springer‎ ‎Heidelberg. 173 S. Hougardy (2006). Classes of perfect graphs. Discrete Math.. 306, 2529-2571 H. R. ‎Maimani‎, ‎M. R. ‎Pournaki‎ ‎and S. ‎Yassemi (2010). ‎A class of weakly perfect graphs. ‎Czechoslovak Math‎. ‎J‎.. 60, 1037-1041