Permutation Graphs and Petersen Graph

Abstract

It was proved by Ellingham $(1984)$ that every permutation graph either contains a subdivision of the Petersen graph or is edge-$3$-colorable. This theorem is an important partial result of Tutte’s Edge-$3$-Coloring Conjecture and is also very useful in the study of the Cycle Double Cover Conjecture. The main result in this paper is that every permutation graph contains either a subdivision of the Petersen graph or two $4$-circuits and therefore provides an alternative proof of the theorem of Ellingham. A corollary of the main result in this paper is that every uniquely edge-$3$-colorable permutation graph of order at least eight must contain a subdivision of the Petersen graph.