{
  "id": "1512.03787",
  "version": "v1",
  "published": "2015-12-11T20:16:17.000Z",
  "updated": "2015-12-11T20:16:17.000Z",
  "title": "(4,2)-choosability of planar graphs with forbidden structures",
  "authors": [
    "Zhanar Berikkyzy",
    "Christopher Cox",
    "Michael Dairyko",
    "Kirsten Hogenson",
    "Mohit Kumbhat",
    "Bernard Lidický",
    "Kacy Messerschmidt",
    "Kevin Moss",
    "Kathleen Nowak",
    "Kevin F. Palmowski",
    "Derrick Stolee"
  ],
  "comment": "33 pages, 14 figures. Collaboration began in the Iowa State University Discrete Mathematics Working Seminar 2014-2015",
  "categories": [
    "math.CO"
  ],
  "abstract": "All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any $\\ell \\in \\{3,4,5,6,7\\}$, a planar graph is 4-choosable if it is $\\ell$-cycle-free. In terms of constraining the list assignment, one refinement of $k$-choosability is choosability with separation. A graph is $(k,s)$-choosable if the graph is colorable from lists of size $k$ where adjacent vertices have at most $s$ common colors in their lists. Every planar graph is $(4,1)$-choosable, but there exist planar graphs that are not $(4,3)$-choosable. It is an open question whether planar graphs are always $(4,2)$-choosable. A chorded $\\ell$-cycle is an $\\ell$-cycle with one additional edge. We demonstrate for each $\\ell \\in \\{5,6,7\\}$ that a planar graph is $(4,2)$-choosable if it does not contain chorded $\\ell$-cycles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-11T20:16:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C10"
    ],
    "keywords": [
      "planar graph",
      "forbidden structures",
      "received significant attention",
      "list assignment",
      "properties guarantee"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151203787B"
    }
  }
}