Coloring graphs by translates in the circle (Q2033887)

The chromatic number, denoted by \(\chi(G),\) of a graph, \(G,\) is simply the smallest integer \(k\) of colors assigned to all the vertices in \(G\) such that no two adjacent vertices will share the same color. To further enrich this research area, some other related notions have also been suggested: the notion of the circular chromatic number of a graph \(g,\) denoted by \(\chi_c(G),\) can be viewed as a mapping that maps all the vertices in \(G\) to unit-length arcs of a circle with a minimum circumstance \(z\) such that adjacent vertices are mapped to internally distinct arcs of such a circle. An independent set of vertices in a graph is a collection of vertices that are not adjacent to each other. The size of such a set is referred to as its weight. Then, the fractional chromatic number of a graph \(G,\) denoted by \(\chi_f(G),\) is defined as the smallest real number \(z\) for which there is an assignment of non-negative weights to all the independents sets of \(G\) such that the sum of their weights is \(z\) and each vertex belongs to independents sets with a total weight of at least 1. It can be shown that, for each finite and simple graph \(G,\) its circular chromatic number lies between its fractional chromatic number and its chromatic number: \(\chi_f(G) \leq \chi_c(G) \leq \chi(G).\) It is worth pointing out that both inequalities can be strict, and the gap between \(\chi_f(G)\) and \(\chi(G)\) can be arbitrarily large. The vertices of the Kneser graph, \(K(n, k),\) is simply the collection of all the \(k\)-subsets chosen from \(n\) elements, and two vertices are adjacent if the associated \(k\)-subsets are disjoint. It holds that, when \(n \geq 2k,\) \[ \chi_f(K(n, k)= n/k \leq n-2k+2= \chi_c(K(n, k))=\chi(K(n, k)), \] and the inequality is strict for \(n > 2k.\) Starting from the definition of a quite technical notion of a coloring base of a graph, based on the Borel set, the authors formalize the notion of a gyrocoloring of a graph, denoted by \(\sigma_Z(G),\) and recast the above notions of circular and fractional chromatic numbers in terms of this notion of coloring base, and coin another notion of gyrochromatic number, \(\chi_g(G).\) It turns out that, for each finite and simple graph \(G,\) its gyrochromatic number lies in between its fractional chromatic number and its circular chromatic number: \[ \chi_f(G) \leq \chi_g(G) \leq \chi_c(G) \leq \chi(G). \] Several equivalent definitions of this gyrochromatic numbers, as well as some basic properties, are given. And graphs for which its gyrochromatic number is strictly between the fractional chromatic number and the circular chromatic number are constructed, making use of a special case of the Kneser graph, \(K(2k^3+k k^3).\) It is also shown that some graph does not have its \(\chi_g(G)\)-gyrocoloring, since the associated coloring base does not exist. Several open problems are suggested, regarding the relationship among the above and other graph coloring notions, to further our understanding of these notions, and their relationship. This paper is well written organized, but quite technical. For all the details, readers have to consult the original paper, and the references cited within.