{
  "id": "1301.6926",
  "version": "v2",
  "published": "2013-01-29T14:24:03.000Z",
  "updated": "2013-11-15T12:51:30.000Z",
  "title": "On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings",
  "authors": [
    "Louis Esperet",
    "Giuseppe Mazzuoccolo"
  ],
  "comment": "17 pages, 8 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The problem of establishing the number of perfect matchings necessary to cover the edge-set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this paper we prove that deciding whether this number is at most 4 for a given cubic bridgeless graph is NP-complete. We also construct an infinite family $\\cal F$ of snarks (cyclically 4-edge-connected cubic graphs of girth at least five and chromatic index four) whose edge-set cannot be covered by 4 perfect matchings. Only two such graphs were known. It turns out that the family $\\cal F$ also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with $m$ edges has length at least $\\tfrac43m$, and we show that this inequality is strict for graphs of $\\cal F$. We also construct the first known snark with no cycle cover of length less than $\\tfrac43m+2$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-11-15T12:51:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "cubic bridgeless graph",
      "shortest cycle cover problem",
      "perfect matchings necessary",
      "cubic graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.6926E"
    }
  }
}