Flexibility of Planar Graphs -- Sharpening the Tools to Get Lists of Size Four

Abstract

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řák, 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 $\epsilon$-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 $\epsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\epsilon$-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řík and show that planar graphs without $K_4^{-}$ are $\epsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $\epsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $\epsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $\epsilon$-flexible for list size $5$.

18 pages, 4 figures

References in corpus (3)

• Flexibility of triangle-free planar graphs
• Flexibility of planar graphs of girth at least six
• Flexibility of planar graphs without 4-cycles

Cited by in corpus (2)

• Flexible List Colorings in Graphs with Special Degeneracy Conditions
• On Weak Flexibility in Planar Graphs