{
  "id": "1305.2670",
  "version": "v2",
  "published": "2013-05-13T04:08:42.000Z",
  "updated": "2014-01-03T20:21:27.000Z",
  "title": "4-critical graphs on surfaces without contractible (<=4)-cycles",
  "authors": [
    "Zdeněk Dvořák",
    "Bernard Lidický"
  ],
  "comment": "52 pages, 19 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We show that if G is a 4-critical graph embedded in a fixed surface $\\Sigma$ so that every contractible cycle has length at least 5, then G can be expressed as $G=G'\\cup G_1\\cup G_2\\cup ... \\cup G_k$, where $|V(G')|$ and $k$ are bounded by a constant (depending linearly on the genus of $\\Sigma$) and $G_1\\ldots,G_k$ are graphs (of unbounded size) whose structure we describe exactly. The proof is computer-assisted - we use computer to enumerate all plane 4-critical graphs of girth 5 with a precolored cycle of length at most 16, that are used in the basic case of the inductive proof of the statement.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-01-03T20:21:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C10",
      "G.2.2"
    ],
    "keywords": [
      "basic case",
      "contractible cycle",
      "precolored cycle",
      "fixed surface",
      "inductive proof"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 52,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1305.2670D"
    }
  }
}