Flexibility of Planar Graphs – Sharpening the Tools to Get Lists of Size Four
share
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 [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 ε-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 ε-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 K_4^- 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.
READ FULL TEXT