Circular colouring and graph homomorphism (Q4243353)

Extended abstract: For any pair of integers \(p\), \(q\) such that \((p,q)= 1\) and \(p\geq 2q\), the graph \(G^q_p\) has vertices \(\{0,1,\dots, p-1\}\) and edges \(\{ij:q\leq| i-j|\leq p-q\}\). These graphs play the same role in the study of the circular chromatic numbers as that played by the complete graphs in the study of the chromatic numbers. That is, the chromatic number of a graph \(G\) is the smallest integer \(n\) such that there exists a homomorphism from \(G\) to the complete graph \(K_n\), and the circular chromatic number of \(G\) is the smallest rational number \(p/q\) such that there exists a homomorphism from \(G\) to \(G^q_p\). The circular chromatic number was introduced in [\textit{A. Vince}, ``Star chromatic number,'' J. Graph Theory 12, No. 4, 551-559 (1988; Zbl 0658.05028)], where it was proved that for every graph \(G\) a smallest such rational number does in fact exist. The graphs \(G^q_p\) share many properties of the complete graphs. However, there are also striking differences between the graphs \(G^q_p\) and the complete graphs. We prove that for many pairs of integers \(p\), \(q\), one may delete most of the edges of \(G^q_p\) so that the resulting graph still has circular chromatic number \(p/q\). To be precise, we prove that for any number \(r>2\), there exists a rational number \(p/q\) (where \((p,q)= 1\)) which is less than \(r\) but arbitrarily close to \(r\), such that \(G^q_p\) contains a subgraph \(H\) with \(\chi_c(H)= \chi_c(G^q_p)= p/q\) and \(| E(H)|= O(\sqrt{| E(G^q_p)|})\). This is in sharp contrast to the fact that the complete graphs are edge-critical, that is, the deletion of any edge decreases its chromatic number and its circular chromatic number.