Flexibility of planar graphs-Sharpening the tools to get lists of size four

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Flexibility of planar graphs-Sharpening the tools to get lists of size four

Popis výsledku v původním jazyce

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 &quot;enough&apos;&apos;, 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.

Název v anglickém jazyce

Flexibility of planar graphs-Sharpening the tools to get lists of size four

Popis výsledku anglicky

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 &quot;enough&apos;&apos;, 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

1872-6771

Svazek periodika

306

Číslo periodika v rámci svazku

January

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

120-132

Kód UT WoS článku

000712075000001

EID výsledku v databázi Scopus

2-s2.0-85122508527