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∈L(v). In this paper, we look at a variant of the widely studied class of precoloring extension problems from Dvořák, Norin, and Postle (J. Graph Theory, 2019), wherein one must satisfy “enough”, as opposed to all, of the requested set of precolors. A graph G is ɛ-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 ɛ-fraction of the requests in S. It is conjectured that planar graphs are ɛ-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 K4− are ɛ-flexible for list size 5. We also prove that planar graphs without 4-cycles and 3-cycle distance at least 2 are ɛ-flexible for list size 4. Finally, we introduce a new (slightly weaker) form of ɛ-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 ɛ-flexible for list size 5.

For nonnegative integers $k, d_1, \ldots, d_k$, a graph is $(d_1, \ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $i\in\{1, \ldots, k\}$. A class $\mathcal C$ of graphs is balanced $k$-partitionable and unbalanced $k$-partitionable if there exists a nonnegative integer $D$ such that all graphs in $\mathcal C$ are $(D, \ldots, D)$-colorable and $(0, \ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a cycle obstruction set of a class $\mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $\mathcal C$. This paper characterizes all cycle obstruction sets of planar graphs to be balanced $k$-partitionable and unbalanced $k$-partitionable for all $k$; namely, we identify all inclusionwise minimal cycle obstruction sets for all $k$.