An Algorithamic Approach to Permutation Graphs and Its Complexities
Asian Resonance (P: ISSN No. 0976-8602 RNI No. UPENG/2012/42622 VOL.-III, ISSUE-III, JULY-2014 E: ISSN No. 2349-9443 ) Abstract Latha Mohanan Assistant professor, Deptt. of Mathematics and Statistics, Guru Nanak Khalsa College, University of Mumbai. Matunga, Mumbai M. G. Mohanan Associate Professor, Deptt. of Mathematics and Computers, Vivek College, Goregoan (w), University of Mumbai. Mumbai Permutation graph was first introduced by Chartrand and Harary in 1967 and their purpose was to study the cycle permutation graph. This paper definespermutation graph and study its properties and characterisationthrough theorems .It alsodiscuss characterisation of permutation labelling by a theorem .It gives real life application of permutation graph as a class of intersection graphs. It gives a sorting permutation using queues in parallel. It also gives canonical colouring of a permutation graph which gives a minimal colouring.This has given through an algorithm ...