
Tomáš Kaiser

JeanSébastien Sereni

Zelealem B. Yilma
Keywords:
Graph theory, Permutation graph, Petersen subdivision, Cograph
Abstract
A permutation graph is a cubic graph admitting a 1factor $M$ whose complement consists of two chordless cycles. Extending results of Ellingham and of Goldwasser and Zhang, we prove that if $e$ is an edge of $M$ such that every 4cycle containing an edge of $M$ contains $e$, then $e$ is contained in a subdivision of the Petersen graph of a special type. In particular, if the graph is cyclically 5edgeconnected, then every edge of $M$ is contained in such a subdivision. Our proof is based on a characterization of cographs in terms of twin vertices. We infer a linear lower bound on the number of Petersen subdivisions in a permutation graph with no 4cycles, and give a construction showing that this lower bound is tight up to a constant factor.