{
  "id": "1501.00860",
  "version": "v1",
  "published": "2015-01-05T13:44:02.000Z",
  "updated": "2015-01-05T13:44:02.000Z",
  "title": "Petersen cores and the oddness of cubic graphs",
  "authors": [
    "Ligang Jin",
    "Eckhard Steffen"
  ],
  "comment": "12 pages, 8 figures, an extended abstract appears in the conference BGW 2014",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a bridgeless cubic graph. Consider a list of $k$ 1-factors of $G$. Let $E_i$ be the set of edges contained in precisely $i$ members of the $k$ 1-factors. Let $\\mu_k(G)$ be the smallest $|E_0|$ over all lists of $k$ 1-factors of $G$. If $G$ is not 3-edge-colorable, then $\\mu_3(G) \\geq 3$. In [E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory (2014) DOI 10.1002/jgt.21798] it is shown that if $\\mu_3(G) \\not = 0$, then $2 \\mu_3(G)$ is an upper bound for the girth of $G$. We show that $\\mu_3(G)$ bounds the oddness $\\omega(G)$ of $G$ as well. We prove that $\\omega(G)\\leq \\frac{2}{3}\\mu_3(G)$. If $\\mu_3(G) = \\frac{2}{3} \\mu_3(G)$, then every $\\mu_3(G)$-core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4-edge-connected cubic graph $G$ with $\\omega(G) = \\frac{2}{3}\\mu_3(G)$. On the other hand, the difference between $\\omega(G)$ and $\\frac{2}{3}\\mu_3(G)$ can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer $k\\geq 3$, there exists a bridgeless cubic graph $G$ such that $\\mu_3(G)=k$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-01-05T13:44:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70"
    ],
    "keywords": [
      "bridgeless cubic graph",
      "cores petersen cores",
      "graph theory",
      "upper bound",
      "specific structure"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150100860J"
    }
  }
}