{
  "id": "1302.2158",
  "version": "v3",
  "published": "2013-02-08T21:25:22.000Z",
  "updated": "2016-01-06T15:13:42.000Z",
  "title": "Three-coloring triangle-free graphs on surfaces II. 4-critical graphs in a disk",
  "authors": [
    "Zdenek Dvorak",
    "Daniel Kral",
    "Robin Thomas"
  ],
  "comment": "45 pages, 2 figures This version: Minor fix to the statement of one lemma, bibliography update",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let G be a plane graph of girth at least five. We show that if there exists a 3-coloring phi of a cycle C of G that does not extend to a 3-coloring of G, then G has a subgraph H on O(|C|) vertices that also has no 3-coloring extending phi. This is asymptotically best possible and improves a previous bound of Thomassen. In the next paper of the series we will use this result and the attendant theory to prove a generalization to graphs on surfaces with several precolored cycles.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-05-25T15:28:37.000Z",
      "comment": "45 pages, 2 figures",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2016-01-06T15:13:42.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C10",
      "G.2.2"
    ],
    "keywords": [
      "three-coloring triangle-free graphs",
      "plane graph",
      "attendant theory",
      "precolored cycles",
      "extending phi"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 45,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.2158D"
    }
  }
}