{
  "id": "1302.2599",
  "version": "v1",
  "published": "2013-02-11T20:15:58.000Z",
  "updated": "2013-02-11T20:15:58.000Z",
  "title": "$(3,1)^*$-choosability of planar graphs without adjacent short cycles",
  "authors": [
    "Min Chen",
    "Andre Raspaud"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A list assignment of a graph $G$ is a function $L$ that assigns a list $L(v)$ of colors to each vertex $v\\in V(G)$. An $(L,d)^*$-coloring is a mapping $\\pi$ that assigns a color $\\pi(v)\\in L(v)$ to each vertex $v\\in V(G)$ so that at most $d$ neighbors of $v$ receive color $\\pi(v)$. A graph $G$ is said to be $(k,d)^*$-choosable if it admits an $(L,d)^*$-coloring for every list assignment $L$ with $|L(v)|\\ge k$ for all $v\\in V(G)$. In 2001, Lih et al. \\cite{LSWZ-01} proved that planar graphs without 4- and $l$-cycles are $(3,1)^*$-choosable, where $l\\in \\{5,6,7\\}$. Later, Dong and Xu \\cite{DX-09} proved that planar graphs without 4- and l-cycles are $(3,1)^*$-choosable, where $l\\in \\{8,9\\}$. There exist planar graphs containing 4-cycles that are not $(3,1)^*$-choosable (Crown, Crown and Woodall, 1986 \\cite{CCW-86}). This partly explains the fact that in all above known sufficient conditions for the $(3,1)^*$-choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles. More precisely, we prove that every planar graph without 4-cycles adjacent to 3- and 4-cycles is $(3,1)^*$-choosable. This is a common strengthening of all above mentioned results. Moreover as a consequence we give a partial answer to a question of Xu and Zhang \\cite{XZ-07} and show that every planar graph without 4-cycles is $(3,1)^*$-choosable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-02-11T20:15:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "planar graph",
      "adjacent short cycles",
      "choosability",
      "list assignment",
      "sufficient conditions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.2599C"
    }
  }
}