{
  "id": "1505.07296",
  "version": "v1",
  "published": "2015-05-27T12:58:50.000Z",
  "updated": "2015-05-27T12:58:50.000Z",
  "title": "Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles",
  "authors": [
    "Zdeněk Dvořák",
    "Bernard Lidický"
  ],
  "comment": "12 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study 3-coloring properties of triangle-free planar graphs $G$ with two precolored 4-cycles $C_1$ and $C_2$ that are far apart. We prove that either every precoloring of $C_1\\cup C_2$ extends to a 3-coloring of $G$, or $G$ contains one of two special substructures which uniquely determine which 3-colorings of $C_1\\cup C_2$ extend. As a corollary, we prove that there exists a constant $D>0$ such that if $H$ is a planar triangle-free graph and $S\\subseteq V(H)$ consists of vertices at pairwise distances at least $D$, then every precoloring of $S$ extends to a 3-coloring of $H$. This gives a positive answer to a conjecture of Dvo\\v{r}\\'ak, Kr\\'al' and Thomas, and implies an exponential lower bound on the number of 3-colorings of triangle-free planar graphs of bounded maximum degree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-05-27T12:58:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C75",
      "G.2.2"
    ],
    "keywords": [
      "planar triangle-free graph",
      "fine structure",
      "triangle-free planar graphs",
      "exponential lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150507296D"
    }
  }
}