Chromatic and clique numbers of a class of perfect graphs

Document Type: Research Paper

Author

Azad University, Chaluse Branch

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 $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‎.

Keywords

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