{
  "id": "1007.1615",
  "version": "v1",
  "published": "2010-07-09T15:49:18.000Z",
  "updated": "2010-07-09T15:49:18.000Z",
  "title": "Linear Choosability of Sparse Graphs",
  "authors": [
    "Daniel W. Cranston",
    "Gexin Yu"
  ],
  "comment": "12 pages, 2 figures",
  "journal": "Discrete Math. Vol. 311, no. 17, 2011, pp. 1910-1917",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study the linear list chromatic number, denoted $\\lcl(G)$, of sparse graphs. The maximum average degree of a graph $G$, denoted $\\mad(G)$, is the maximum of the average degrees of all subgraphs of $G$. It is clear that any graph $G$ with maximum degree $\\Delta(G)$ satisfies $\\lcl(G)\\ge \\ceil{\\Delta(G)/2}+1$. In this paper, we prove the following results: (1) if $\\mad(G)<12/5$ and $\\Delta(G)\\ge 3$, then $\\lcl(G)=\\ceil{\\Delta(G)/2}+1$, and we give an infinite family of examples to show that this result is best possible; (2) if $\\mad(G)<3$ and $\\Delta(G)\\ge 9$, then $\\lcl(G)\\le\\ceil{\\Delta(G)/2}+2$, and we give an infinite family of examples to show that the bound on $\\mad(G)$ cannot be increased in general; (3) if $G$ is planar and has girth at least 5, then $\\lcl(G)\\le\\ceil{\\Delta(G)/2}+4$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-07-09T15:49:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "sparse graphs",
      "linear choosability",
      "linear list chromatic number",
      "maximum average degree",
      "infinite family"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1007.1615C"
    }
  }
}