Coloring graphs by translates in the circle
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: th...
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
27 April 2021
|
| In: |
European journal of combinatorics
Year: 2021, Volume: 96, Pages: 1-18 |
| DOI: | 10.1016/j.ejc.2021.103346 |
| Online Access: | Resolving-System, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.ejc.2021.103346 Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S019566982100038X 
|
| Author Notes: | Pablo Candela, Carlos Catalá, Robert Hancock, Adam Kabela, Daniel Král’, Ander Lamaison, Lluís Vena |
| Summary: | 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 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. |
|---|---|
| Item Description: | Gesehen am 20.07.2022 |
| Physical Description: | Online Resource |
| DOI: | 10.1016/j.ejc.2021.103346 |