{
  "id": "1204.1989",
  "version": "v1",
  "published": "2012-04-09T20:53:18.000Z",
  "updated": "2012-04-09T20:53:18.000Z",
  "title": "Multiple Petersen subdivisions in permutation graphs",
  "authors": [
    "Tomáš Kaiser",
    "Jean-Sébastien Sereni",
    "Zelealem Yilma"
  ],
  "categories": [
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-04-09T20:53:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99",
      "05C75"
    ],
    "keywords": [
      "permutation graph",
      "multiple petersen subdivisions",
      "linear lower bound",
      "complement consists",
      "constant factor"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1204.1989K"
    }
  }
}