Coloring graphs by translates in the circle
| Autoři | |
|---|---|
| Rok publikování | 2021 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | European Journal of Combinatorics |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.1016/j.ejc.2021.103346 |
| Doi | http://dx.doi.org/10.1016/j.ejc.2021.103346 |
| Klíčová slova | chromatic numbers |
| Popis | 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. |
| Související projekty: |