Some results on the graph of derangements

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 ۵, \Gamma(D_n) is neither a perfect graph nor a cograph. Moreover, this graph can not be a line graph unless n\leq ۴. Maximum cliques and maximum independent sets are studied, too.

کلیدواژه ها:

Clique number ، Graph of derangements ، Independence number