Flexibility of planar graphs without 4-cycles

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

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

Flexibility of planar graphs without 4-cycles

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Flexibility of planar graphs without 4-cycles

Popis výsledku anglicky

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.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

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

Acta Mathematica Universitatis Comenianae

ISSN

0862-9544

e-ISSN

—

Svazek periodika

88

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

SK - Slovenská republika

Počet stran výsledku

6

Strana od-do

935-940

Kód UT WoS článku

000484349000090

EID výsledku v databázi Scopus

2-s2.0-85074030496