Multiple Petersen Subdivisions in Permutation Graphs

Abstract

A permutation graph is a cubic graph admitting a 1-factor $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 4-cycle 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 5-edge-connected, 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 4-cycles, and give a construction showing that this lower bound is tight up to a constant factor.