On Weak Flexibility in Planar Graphs

dc.contributor.author Lidicky, Bernard
dc.contributor.author Lidicky, Bernard
dc.contributor.author Masarík, Tomáš
dc.contributor.author Murphy, Kyle
dc.contributor.author Zerbib, Shira
dc.contributor.department Mathematics
dc.date 2020-09-22T17:58:21.000
dc.date.accessioned 2021-02-26T02:54:43Z
dc.date.available 2021-02-26T02:54:43Z
dc.date.copyright Wed Jan 01 00:00:00 UTC 2020
dc.date.issued 2020-09-16
dc.description.abstract <p>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.</p> <p>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.</p> <p>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.</p>
dc.description.comments <p>This preprint is made available though arXiv: <a href="https://arxiv.org/abs/2009.07932" target="_blank">https://arxiv.org/abs/2009.07932</a>. </p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/math_pubs/258/
dc.identifier.articleid 1265
dc.identifier.contextkey 19510268
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath math_pubs/258
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/96653
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/math_pubs/258/2020_Lidicky_WeakFlexibilityPreprint.pdf|||Fri Jan 14 22:59:41 UTC 2022
dc.subject.disciplines Discrete Mathematics and Combinatorics
dc.subject.disciplines Mathematics
dc.title On Weak Flexibility in Planar Graphs
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication a1d8f5ab-9124-4104-981c-8ba1e426e3ff
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
847.27 KB
Adobe Portable Document Format