Fay Ye

The Instruction of Permutation Graphs

Permutation graphs, a type of graph associated with permutations, was first introduced in 1967 by Chartrand and Harary. In this presentation, we briefly give an introduction of the permutation graph, and some interesting characteristic features such as reverse property and transitive orientation property. We construct a permutation according to a comparability graph and its complement. In addition, we show that the technic can be applied in the real-world industry issue such as scheduling the airlines between among of cities. Finally, we demonstrate an algorithm of sorting a permutation, and present the relationship between the chromatic number and the minimum required number of the queues to sort the permutation. By that, we present another algorithm for colouring a permutation graph and show its complexity.