Can I read Flexibility of Planar Graphs -- Sharpening the Tools to Get Lists of Size Four on EtoBox?

Flexibility of Planar Graphs -- Sharpening the Tools to Get Lists of Size Four by Choi, Ilkyoo; Clemen, Felix Christian; Ferrara, Michael; Horn, Paul; Ma, Fuhong; Masařík, Tomáš is a scholarly article available to read on EtoBox.

What is Flexibility of Planar Graphs -- Sharpening the Tools to Get Lists of Size Four about?

A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $c\in L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvo\v{r}\'ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph $G$ is $\varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $\varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masa\v{r}\'ik and show

Author

Choi, Ilkyoo; Clemen, Felix Christian; Ferrara, Michael; Horn, Paul; Ma, Fuhong; Masařík, Tomáš

Published

2020

Language

EN