Skip to main content
Article
On Weak Flexibility in Planar Graphs
arXiv
  • Bernard Lidicky, Iowa State University
  • Tomáš Masarík, University of Warsaw
  • Kyle Murphy, Iowa State University
  • Shira Zerbib, Iowa State University
Document Type
Article
Publication Version
Submitted Manuscript
Publication Date
9-16-2020
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.

Comments

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

Copyright Owner
The Authors
Language
en
File Format
application/pdf
Citation Information
Bernard Lidicky, Tomáš Masarík, Kyle Murphy and Shira Zerbib. "On Weak Flexibility in Planar Graphs" arXiv (2020)
Available at: http://works.bepress.com/bernard-lidicky/66/