Multiple Petersen subdivisions in permutation graphs (Q1953423)

Summary: A permutation graph is a cubic graph admitting a 1-factor \(M\) whose complement consists of two chordless cycles. Extending results of \textit{M. N. Ellingham} [Congr. Numerantium 44, 33--40 (1984; Zbl 0558.05040)] and of \textit{J. L. Goldwasser} and \textit{C.-Q. Zhang} [Ars Comb. 51, 240--248 (1999; Zbl 0977.05067)], 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.