{
  "id": "2408.08393",
  "version": "v1",
  "published": "2024-08-15T19:36:32.000Z",
  "updated": "2024-08-15T19:36:32.000Z",
  "title": "Graphs of maximum average degree less than $\\frac {11}{3}$ are flexibly $4$-choosable",
  "authors": [
    "Richard Bi",
    "Peter Bradshaw"
  ],
  "comment": "34 pages + appendix",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the flexible list coloring problem, in which we have a graph $G$, a color list assignment $L:V(G) \\rightarrow 2^{\\mathbb N}$, and a set $U \\subseteq V(G)$ of vertices such that each $u \\in U$ has a preferred color $p(u) \\in L(u)$. Given a constant $\\varepsilon > 0$, the problem asks for an $L$-coloring of $G$ in which at least $\\varepsilon |U|$ vertices in $U$ receive their preferred color. We use a method of reducible subgraphs to approach this problem. We develop a vertex-partitioning tool that, when used with a new reducible subgraph framework, allows us to define large reducible subgraphs. Using this new tool, we show that if $G$ has maximum average degree less than $\\frac{11}{3}$, a list $L(v)$ of size $4$ at each $v \\in V(G)$, and a set $U \\subseteq V(G)$ of vertices with preferred colors, then there exists an $L$-coloring of $G$ for which at least $2^{-145} |U|$ vertices of $U$ receive their preferred color.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-15T19:36:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "maximum average degree",
      "preferred color",
      "color list assignment",
      "define large reducible subgraphs",
      "flexible list coloring problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}