Single-conflict colouring
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Single-conflict colouring
Original language description
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.
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
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2021
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
Journal of Graph Theory
ISSN
0364-9024
e-ISSN
1097-0118
Volume of the periodical
97
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
13
Pages from-to
148-160
UT code for WoS article
000585085100001
EID of the result in the Scopus database
2-s2.0-85096659441