Coloring graphs by translates in the circle. (August 2021)

• Record Type: Journal Article
• Authors: Candela, Pablo; Catalá, Carlos; Hancock, Robert; Kabela, Adam; Král', Daniel; Lamaison, Ander; Vena, Lluís
• Is Part Of: European journal of combinatorics. Volume 96(2021)
• Publication Date: 2021-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103346
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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.