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 ...

Get Algorithmic Graph Theory and Perfect Graphs, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.