{
  "id": "1203.3912",
  "version": "v2",
  "published": "2012-03-18T03:13:47.000Z",
  "updated": "2012-05-22T17:03:39.000Z",
  "title": "Odd cycle transversals and independent sets in fullerene graphs",
  "authors": [
    "Luerbio Faria",
    "Sulamita Klein",
    "Matěj Stehlík"
  ],
  "comment": "13 pages, 4 figures",
  "journal": "SIAM Journal on Discrete Mathematics 26(3): 1458-1469, 2012",
  "doi": "10.1137/120870463",
  "categories": [
    "math.CO"
  ],
  "abstract": "A fullerene graph is a cubic bridgeless plane graph with all faces of size 5 and 6. We show that that every fullerene graph on n vertices can be made bipartite by deleting at most sqrt{12n/5} edges, and has an independent set with at least n/2-sqrt{3n/5} vertices. Both bounds are sharp, and we characterise the extremal graphs. This proves conjectures of Doslic and Vukicevic, and of Daugherty. We deduce two further conjectures on the independence number of fullerene graphs, as well as a new upper bound on the smallest eigenvalue of a fullerene graph.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-05-22T17:03:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38"
    ],
    "keywords": [
      "fullerene graph",
      "odd cycle transversals",
      "independent set",
      "cubic bridgeless plane graph",
      "smallest eigenvalue"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.3912F"
    }
  }
}