Coloring graphs by translates in the circle

J 2021

Coloring graphs by translates in the circle

CANDELA, Pablo; Carlos CATALÁ; Robert Arthur HANCOCK; Adam KABELA; Daniel KRÁĽ et. al.

Basic information

Original name

Coloring graphs by translates in the circle

Authors

CANDELA, Pablo; Carlos CATALÁ; Robert Arthur HANCOCK (826 United Kingdom of Great Britain and Northern Ireland, belonging to the institution); Adam KABELA (203 Czech Republic, belonging to the institution); Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution); Ander LAMAISON VIDARTE (724 Spain, belonging to the institution) and Lluís VENA

Edition

European Journal of Combinatorics, LONDON, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2021, 0195-6698

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

is not subject to a state or trade secret

References:

URL

Impact factor

Impact factor: 0.890

RIV identification code

RIV/00216224:14330/21:00124666

Organization unit

Faculty of Informatics

DOI

https://doi.org/10.1016/j.ejc.2021.103346

UT WoS

000659230400014

EID Scopus

2-s2.0-85190462733

Keywords in English

chromatic numbers

Abstract

In the original language

The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighboring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number & nbsp;is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.

Links

MUNI/I/1677/2018, interní kód MU

Name: MUNI AWARD in Science and Humanitites 1 (Acronym: MASH 1)

Investor: Masaryk University, MASH - MUNI Award in Science and Humanities

Cite

CANDELA, Pablo; Carlos CATALÁ; Robert Arthur HANCOCK; Adam KABELA; Daniel KRÁĽ; Ander LAMAISON VIDARTE and Lluís VENA. Coloring graphs by translates in the circle. European Journal of Combinatorics. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2021, vol. 96, No 103346, p. 1-18. ISSN 0195-6698. Available from: https://doi.org/10.1016/j.ejc.2021.103346.

@article{1824817,
   author = {Candela, Pablo and Catalá, Carlos and Hancock, Robert Arthur and Kabela, Adam and Kráľ, Daniel and Lamaison Vidarte, Ander and Vena, Lluís},
   article_location = {LONDON},
   article_number = {103346},
   doi = {https://doi.org/10.1016/j.ejc.2021.103346},
   keywords = {chromatic numbers},
   language = {eng},
   issn = {0195-6698},
   journal = {European Journal of Combinatorics},
   title = {Coloring graphs by translates in the circle},
   url = {http://dx.doi.org/10.1016/j.ejc.2021.103346},
   volume = {96},
   year = {2021}
}

TY  - JOUR
ID  - 1824817
AU  - Candela, Pablo - Catalá, Carlos - Hancock, Robert Arthur - Kabela, Adam - Kráľ, Daniel - Lamaison Vidarte, Ander - Vena, Lluís
PY  - 2021
TI  - Coloring graphs by translates in the circle
JF  - European Journal of Combinatorics
VL  - 96
IS  - 103346
SP  - 1-18
EP  - 1-18
PB  - ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
SN  - 01956698
KW  - chromatic numbers
UR  - http://dx.doi.org/10.1016/j.ejc.2021.103346
N2  - The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighboring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number & nbsp;is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.
ER  -

CANDELA, Pablo; Carlos CATALÁ; Robert Arthur HANCOCK; Adam KABELA; Daniel KRÁĽ; Ander LAMAISON VIDARTE and Lluís VENA. Coloring graphs by translates in the circle. \textit{European Journal of Combinatorics}. LONDON: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2021, vol.~96, No~103346, p.~1-18. ISSN~0195-6698. Available from: https://doi.org/10.1016/j.ejc.2021.103346.

Přehled o publikaci