Flexibility of planar graphs without 4-cycles
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404208" target="_blank" >RIV/00216208:11320/19:10404208 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8NWnbInaOL" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8NWnbInaOL</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Flexibility of planar graphs without 4-cycles
Original language description
Proper graph coloring assigns different colors to adjacent vertices ofthe graph. Usually, the number of colors is fixed or as small as possible. Considerapplications (e.g. variants of scheduling) where colors represent limited resourcesand graph represents conflicts, i.e., two adjacent vertices cannot obtain the sameresource. In such applications, it is common that some vertices have preferredresource(s). However, unfortunately, it is not usually possible to satisfy all suchpreferences. The notion called flexibility was recently defined in [Dvořák, Norin,Postle: List coloring with requests, Journal of Graph Theory 2019]. There insteadof satisfying all the preferences the aim is to satisfy at least a constant fraction ofthe request. Recently, the structural properties of planar graphs in terms of flexibility wereinvestigated. We continue this line of research. Let G be a planar graph with a listassignment L. Suppose a preferred color is given for some of the vertices. We provethat if G is a planar graph without 4-cycles and all lists have size at least five, thenthere exists an L-coloring respecting at least a constant fraction of the preferences.
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
10101 - Pure mathematics
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2019
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
Acta Mathematica Universitatis Comenianae
ISSN
0862-9544
e-ISSN
—
Volume of the periodical
88
Issue of the periodical within the volume
3
Country of publishing house
SK - SLOVAKIA
Number of pages
6
Pages from-to
935-940
UT code for WoS article
000484349000090
EID of the result in the Scopus database
2-s2.0-85074030496