Circular chromatic number: A survey (Q5931460)

The circular chromatic number (also called star chromatic number) is a refinement of the chromatic number of a graph. If \(k\) and \(d\) are positive integers with \(k \geq 2d\) then a (\(k,d\))-coloring of a graph \(G\) is an assignment \(f\) of colors \(0,1, \dots ,k-1\) to the vertices of \(G\) such that \(d \leq |f(x)-f(y)|\leq k-d\) whenever two vertices \(x\) and \(y\) are adjacent. The circular chromatic number \(\chi_c (G)\) of \(G\) is defined by \(\chi_c (G)=\inf\{k/d: G\) has a \((k,d)\)-coloring\}. Obviously, a (\(k,1\))-coloring is an ordinary \(k\)-coloring of \(G\). The concept of (\(k,d\))-colorings was introduced by \textit{A. Vince} [J. Graph Theory 12, No. 4, 551-559 (1988; Zbl 0658.05028)]. In this paper different definitions of the circular chromatic number are mentioned (and proved to be equivalent) and results on this topic are surveyed. The author concentrates on the relations among the circular chromatic number, the chromatic number and some other graph parameters including the fractional chromatic number, the clique number, the maximum degree, the girth and the connectivity. Moreover, \(\chi_c (G)\) is determined for some classes of graphs. The paper concludes by posing 28 open problems and gathering more than 100 papers on the topic.