Single-conflict colouring

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10448434" target="_blank" >RIV/00216208:11320/21:10448434 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=R_7Q8IJ4r8" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=R_7Q8IJ4r8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/jgt.22646" target="_blank" >10.1002/jgt.22646</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Single-conflict colouring

Popis výsledku v původním jazyce

Given a multigraph, suppose that each vertex is given a local assignment of (Formula presented.) colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least (Formula presented.) for which this is always possible given any set of local assignments we call the single-conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus (Formula presented.) is (Formula presented.) as (Formula presented.). This is sharp up to the logarithmic factor.

Název v anglickém jazyce

Single-conflict colouring

Popis výsledku anglicky

Given a multigraph, suppose that each vertex is given a local assignment of (Formula presented.) colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least (Formula presented.) for which this is always possible given any set of local assignments we call the single-conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus (Formula presented.) is (Formula presented.) as (Formula presented.). This is sharp up to the logarithmic factor.

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

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

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

Journal of Graph Theory

ISSN

0364-9024

e-ISSN

1097-0118

Svazek periodika

97

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

13

Strana od-do

148-160

Kód UT WoS článku

000585085100001

EID výsledku v databázi Scopus

2-s2.0-85096659441