فهرست نشریات علمی دسترسی آزاد ایران

The graph of derangements, denoted by $\Gamma(D_n)$, is a simple graph whose vertex set is the set of all derangements on $[n]$ and two distinct vertices $f$ and $g$ are adjacent if and only if $f(i)\neq g(i)$, for every $i\in [n]$. In this paper, some properties of this graph are presented. The clique number and the vertex chromatic number of this graph are determined. Then we show that for every positive integer $n\geq 5$, $\Gamma(D_n)$ is neither a perfect graph nor a cograph. Moreover, this graph can not be a line graph unless $n\leq 4$. Maximum cliques and maximum independent sets are studied, too.