Transitive multipermutation graphs: Case \(4\leq n\leq m\) (Q1183982)

Multipermutation graphs are a generalization of permutation graphs defined by C. Chartrand and F. Harary. In this paper the chromatic numbers of transitive multipermutation graphs are investigated. It is shown that for every graph \(G\) having chromatic number \(n\) the transitive multipermutation graph \(J_ m(G)\) of \(G\) has chromatic number \(X(J_ m)\) in between \(m\) and \(m+n-1\) if \(4\leq n\leq m\), and in between \(n\) and \(2n\) if \(4\leq n=m\), where these bounds are all the best possible.