Flexibility of planar graphs-Sharpening the tools to get lists of size four
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455170" target="_blank" >RIV/00216208:11320/22:10455170 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=gC5wMmFvJZ" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=gC5wMmFvJZ</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2021.09.021" target="_blank" >10.1016/j.dam.2021.09.021</a>
Alternative languages
Result language
angličtina
Original language name
Flexibility of planar graphs-Sharpening the tools to get lists of size four
Original language description
A graph where each vertex v has a list L(v) of available colors is L-colorable if there is a proper coloring such that the color of v is in L(v) for each v. A graph is k-choosable if every assignment L of at least k colors to each vertex guarantees an L-coloring. Given a list assignment L, an L-request for a vertex v is a color c is an element of L(v). In this paper, we look at a variant of the widely studied class of precoloring extension problems from Dvorak, Norin, and Postle (J. Graph Theory, 2019), wherein one must satisfy "enough'', as opposed to all, of the requested set of precolors. A graph G is epsilon-flexible for list size k if for any k-list assignment L, and any set S of L-requests, there is an L-coloring of G satisfying epsilon-fraction of the requests in S. It is conjectured that planar graphs are epsilon-flexible for list size 5, yet it is proved only for list size 6 and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masarik and show that planar graphs without K-4(-) are epsilon-flexible for list size 5. We also prove that planar graphs without 4-cycles and 3-cycle distance at least 2 are epsilon-flexible for list size 4. Finally, we introduce a new (slightly weaker) form of epsilon-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are epsilon-flexible for list size 5. (C) 2021 The Author(s). Published by Elsevier B.V.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Discrete Applied Mathematics
ISSN
0166-218X
e-ISSN
1872-6771
Volume of the periodical
306
Issue of the periodical within the volume
January
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
13
Pages from-to
120-132
UT code for WoS article
000712075000001
EID of the result in the Scopus database
2-s2.0-85122508527