On Weak Flexibility in Planar Graphs

Lidicky, Bernard
Masarík, Tomáš
Murphy, Kyle
Zerbib, Shira
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Journal Issue

Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs [JGT 19']. In this new setting, each vertex v in some subset of V(G) has a request for a certain color r(v) in its list of colors L(v). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests.

The main studied question is whether there exists a universal constant ϵ>0 such that any graph G in some graph class C satisfies at least ϵ proportion of the requests. More formally, for k>0 the goal is to prove that for any graph G∈C on vertex set V, with any list assignment L of size k for each vertex, and for every R⊆V and a request vector (r(v):v∈R, r(v)∈L(v)), there exists an L-coloring of G satisfying at least ϵ|R| requests. If this is true, then C is called ϵ-flexible for lists of size k.

Choi et al. [arXiv 20'] introduced the notion of weak flexibility, where R=V. We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists ϵ(b)>0 so that the class of planar graphs without K4,C5,C6,C7,Bb is weakly ϵ(b)-flexible for lists of size 4 (here Kn, Cn and Bn are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without K4,C5,C6,C7,B5 is ϵ-flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable.


This preprint is made available though arXiv: https://arxiv.org/abs/2009.07932.