Article citationsMore>>

A. Pnueli, A. Lempel and S. Even, “Transitive Orientation of Graphs and Identification of Permutation Graphs,” Canadian Journal of Mathematics, Vol. 23, No. 1, 1971, pp 160-175. doi:10.4153/CJM-1971-016-5

has been cited by the following article:

• TITLE: Characterization and Construction of Permutation Graphs

  AUTHORS: Severino V. Gervacio, Teofina A. Rapanut, Phoebe Chloe F. Ramos

  KEYWORDS: Permutation; Inversion; Permutation Graph; Cohesive Order; Oriented Graph; Tournament Score Sequence; Caterpillar; Graph Composition

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.3 No.1, January 29, 2013

  ABSTRACT: If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both the graph and its complement have transitive orientations. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. We show that only the caterpillars are permutation graphs among the trees. A simple method of constructing permutation graphs is also presented here.