{
  "id": "1608.05759",
  "version": "v1",
  "published": "2016-08-19T23:57:02.000Z",
  "updated": "2016-08-19T23:57:02.000Z",
  "title": "Five-list-coloring graphs on surfaces III. One list of size one and one list of size two",
  "authors": [
    "Luke Postle",
    "Robin Thomas"
  ],
  "comment": "17 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a plane graph with outer cycle $C$ and let $(L(v):v\\in V(G))$ be a family of non-empty sets. By an $L$-coloring of $G$ we mean a (proper) coloring $\\phi$ of $G$ such that $\\phi(v)\\in L(v)$ for every vertex $v$ of $G$. Thomassen proved that if $v_1,v_2\\in V(C)$ are adjacent, $L(v_1)\\ne L(v_2)$, $|L(v)|\\ge3$ for every $v\\in V(C)-\\{v_1,v_2\\}$ and $|L(v)|\\ge5$ for every $v\\in V(G)-V(C)$, then $G$ has an $L$-coloring. What happens when $v_1$ and $v_2$ are not adjacent? Then an $L$-coloring need not exist, but in the first paper of this series we have shown that it exists if $|L(v_1)|,|L(v_2)|\\ge2$. Here we characterize when an $L$-coloring exists if $|L(v_1)|\\ge1$ and $|L(v_2)|\\ge2$. This result is a lemma toward a more general theorem along the same lines, which we will use to prove that minimally non-$L$-colorable planar graphs with two precolored cycles of bounded length are of bounded size. The latter result has a number of applications which we pursue elsewhere.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-08-19T23:57:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "five-list-coloring graphs",
      "non-empty sets",
      "plane graph",
      "outer cycle",
      "first paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}