Permutation graphs and Petersen graph (Q2761063)

Let \(G\) be a permutation graph, that is, \(G\) consists of two disjoint cycles of the same size and a matching \(M\) between them (so \(G\) is 3-regular). The authors prove a strengthening of a theorem of \textit{M. N. Ellingham} [Congr. Numerantium 44, 33-40 (1984; Zbl 0558.05040)]: if \(G\) contains no subdivision of the Petersen graph \(P_{10}\) (= permutation graph 14253) then \(G\) contains two distinct 4-cycles. In fact, it suffices to forbid only the subdivisions of \(P_{10}\) formed by the two cycles of \(G\) and some 5 edges of \(M\). This is shown to be best possible. A corollary is derived which says that every uniquely edge-3-colorable permutation graph with at least 8 vertices must contain a subdivision of \(P_{10}\).