Chapter 7
Permutation graphs
Martin Charles Golumbic
Publisher Summary
This chapter presents a class of perfect graphs, which has a large number of applications. An undirected graph G[Π] from Π can be constructed in the following manner: G[Π] has vertices numbered from 1 to n; two vertices are joined by an edge if the larger of their corresponding numbers is to the left of the smaller in Π (that is, they occur out of their proper order reading left to right). The graph G[Π] is sometimes called the inversion graph of Π. Permutation graphs have many interesting properties. When one reverse the sequence K. Each pair of numbers that occurred in the correct order in Π is now in the wrong order, and vice versa. Thus, the permutation graph one obtains is ...
