{
  "id": "2009.07932",
  "version": "v1",
  "published": "2020-09-16T20:49:14.000Z",
  "updated": "2020-09-16T20:49:14.000Z",
  "title": "On Weak Flexibility in Planar Graphs",
  "authors": [
    "Bernard Lidický",
    "Tomáš Masařík",
    "Kyle Murphy",
    "Shira Zerbib"
  ],
  "comment": "30 pages, 9 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Recently, Dvo\\v{r}\\'ak, Norin, and Postle introduced flexibility as an extension of list coloring on graphs [JGT 19']. In this new setting, each vertex $v$ in some subset of $V(G)$ has a request for a certain color $r(v)$ in its list of colors $L(v)$. The goal is to find an $L$ coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $\\epsilon >0$ such that any graph $G$ in some graph class $\\mathcal{C}$ satisfies at least $\\epsilon$ proportion of the requests. More formally, for $k > 0$ the goal is to prove that for any graph $G \\in \\mathcal{C}$ on vertex set $V$, with any list assignment $L$ of size $k$ for each vertex, and for every $R \\subseteq V$ and a request vector $(r(v): v\\in R, ~r(v) \\in L(v))$, there exists an $L$-coloring of $G$ satisfying at least $\\epsilon|R|$ requests. If this is true, then $\\mathcal{C}$ is called $\\epsilon$-flexible for lists of size $k$. Choi et al. [arXiv 20'] introduced the notion of weak flexibility, where $R = V$. We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer $b$ there exists $\\epsilon(b)>0$ so that the class of planar graphs without $K_4, C_5 , C_6 , C_7, B_b$ is weakly $\\epsilon(b)$-flexible for lists of size $4$ (here $K_n$, $C_n$ and $B_n$ are the complete graph, a cycle, and a book on $n$ vertices, respectively). We also show that the class of planar graphs without $K_4, C_5 , C_6 , C_7, B_5$ is $\\epsilon$-flexible for lists of size $4$. The results are tight as these graph classes are not even 3-colorable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-16T20:49:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "planar graphs",
      "graph class",
      "handle weak flexibility",
      "complete graph",
      "list assignment"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}