On Weak Flexibility in Planar Graphs

Thumbnail Image
Date
2020-09-16
Authors
Masarík, Tomáš
Murphy, Kyle
Zerbib, Shira
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Person
Lidicky, Bernard
Professor
Research Projects
Organizational Units
Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Department
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.

Description
Keywords
Citation
DOI
Source
Copyright
Wed Jan 01 00:00:00 UTC 2020
Collections