Back to Search Start Over

Coloring graphs by translates in the circle

Authors :
Candela, Pablo
Catala, Carlos
Hancock, Robert
Kabela, Adam
Kral, Daniel
Lamaison, Ander
Vena, Lluis
Publication Year :
2020

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 neighbouring 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.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2004.01145
Document Type :
Working Paper