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.
Tomáš Kaiser
1
;
Jean-Sébastien Sereni
2
;
Zelealem B. Yilma
2
1
University of West Bohemia, Pilsen
2
CNRS (LIAFA, Univ. Paris Diderot), Paris
Tomáš Kaiser; Jean-Sébastien Sereni; Zelealem B. Yilma. Multiple Petersen subdivisions in permutation graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2239
@article{10_37236_2239,
author = {Tom\'a\v{s} Kaiser and Jean-S\'ebastien Sereni and Zelealem B. Yilma},
title = {Multiple {Petersen} subdivisions in permutation graphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2239},
zbl = {1266.05172},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2239/}
}
TY - JOUR
AU - Tomáš Kaiser
AU - Jean-Sébastien Sereni
AU - Zelealem B. Yilma
TI - Multiple Petersen subdivisions in permutation graphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2239/
DO - 10.37236/2239
ID - 10_37236_2239
ER -
%0 Journal Article
%A Tomáš Kaiser
%A Jean-Sébastien Sereni
%A Zelealem B. Yilma
%T Multiple Petersen subdivisions in permutation graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2239/
%R 10.37236/2239
%F 10_37236_2239
