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 permutati...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.展开更多
文摘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.
