#### Campus Units

Mathematics

#### Document Type

Article

#### Publication Version

Submitted Manuscript

#### Publication Date

9-16-2020

#### Journal or Book Title

arXiv

#### Abstract

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.

#### Copyright Owner

The Authors

#### Copyright Date

2020

#### Language

en

#### File Format

application/pdf

#### Recommended Citation

Lidicky, Bernard; Masarík, Tomáš; Murphy, Kyle; and Zerbib, Shira, "On Weak Flexibility in Planar Graphs" (2020). *Mathematics Publications*. 258.

https://lib.dr.iastate.edu/math_pubs/258

## Comments

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