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 is an element of L(v). In this paper, we look at a variant of the widely studied class of precoloring extension problems from Dvorak, 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 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 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 Masarik 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. (C) 2021 The Author(s).
Published by Elsevier B.V.