Circular coloring

{{infobox graph | name = Circular complete graph | vertices = n | edges = n(n − 2k + 1) / 2 | chromatic_number = ⌈n/k⌉ | girth = \left\{\begin{array}{ll}\infty & n = 2k\\ n & n = 2k+1\\ 4 & 2k+2 \leq n | notation = K_{n/k} | properties = -regularVertex-transitiveCirculantHamiltonian }} For integers n,k such that n\ge 2k, the circular complete graph K_{n/k} (also known as a circular clique) is the graph with vertex set \Z/n\Z=\{0,1, \ldots, n-1\} and edges between elements at distance \ge k. That is vertex i is adjacent to: :i+k, i+k+1, \ldots, i+n-k \bmod n. K_{n/1} is just the complete graph , while K_{2n+1/n} is the cycle graph C_{2n+1}. A circular coloring is then, according to the second definition above, a homomorphism into a circular complete graph. The crucial fact about these graphs is that K_{a/b} admits a homomorphism into K_{c/d} if and only if \tfrac{a}{b} \le \tfrac{c}{d}. This justifies the notation, since if \tfrac{a}{b} = \tfrac{c}{d} then K_{a/b} and K_{c/d} are homomorphically equivalent. Moreover, the homomorphism order among them refines the order given by complete graphs into a dense order, corresponding to rational numbers \ge 2. For example :K_{2/1} \to K_{7/3} \to K_{5/2} \to \cdots \to K_{3/1} \to K_{4/1} \to \cdots or equivalently :K_2 \to C_7 \to C_5 \to \cdots \to K_3 \to K_4 \to \cdots The example on the figure can be interpreted as a homomorphism from the flower snark into , which comes earlier than K_3 corresponding to the fact that \chi_c(J_5) \le 2.5 ==See also==