Circular chromatic numbers of Mycielski's graphs (Q1301826): Difference between revisions

Let \(k\) and \(d\) be integers such that \(0< d\leq k\). A \((k,d)\)-colouring of a graph \(G\) is a colouring \(c\) of the vertices of \(G\) with \(k\) colours \(0,1,\dots, k-1\) such that for any edge \(xy\), we have \(d\leq|c(x)- c(y)|\leq k-d\). The circular chromatic number \(\chi_c(G)\) of \(G\) is the minimum ratio \(k/d\) for which there exists a \((k,d)\)-colouring of \(G\). In some sense the circular chromatic number is a refinement of the chromatic number of a graph. It contains more information about the graph. The problem of determining if \(\chi_c(G)= \chi(G)\) or \(\chi_c(G)\) is ``close to'' \(\chi(G)- 1\) is hard. In this direction the authors report some progress for Mycielski's graphs.