Coloring graphs by translates in the circle
| Authors | |
|---|---|
| Year of publication | 2021 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.1016/j.ejc.2021.103346 |
| Doi | http://dx.doi.org/10.1016/j.ejc.2021.103346 |
| Keywords | chromatic numbers |
| Description | 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. |
| Related projects: |