On Weak Flexibility in Planar Graphs
share
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 𝒞 satisfies at least ϵ proportion of the requests. More formally, for k > 0 the goal is to prove that for any graph G ∈𝒞 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 𝒞 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 K_4, C_5 , C_6 , C_7, B_b is weakly ϵ(b)-flexible for lists of size 4 (here K_n, C_n and B_n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without K_4, C_5 , C_6 , C_7, B_5 is ϵ-flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable.
READ FULL TEXT