Circular coloring

In graph theory, circular coloring may be viewed as a refinement of usual graph coloring. The circular chromatic number of a graph ${\displaystyle G}$, denoted ${\displaystyle \chi _{c}(G)}$ can be given by any of the following definitions, all of which are equivalent (for finite graphs).

1. ${\displaystyle \chi _{c}(G)}$ is the infimum over all real numbers ${\displaystyle r}$ so that there exists a map from ${\displaystyle V(G)}$ to a circle of circumference 1 with the property that any two adjacent vertices map to points at distance ${\displaystyle \geq {\tfrac {1}{r}}}$ along this circle.
2. ${\displaystyle \chi _{c}(G)}$ is the infimum over all rational numbers ${\displaystyle {\tfrac {n}{k}}}$ so that there exists a map from ${\displaystyle V(G)}$ to the cyclic group ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ with the property that adjacent vertices map to elements at distance ${\displaystyle \geq k}$ apart.
3. In an oriented graph, declare the imbalance of a cycle ${\displaystyle C}$ to be ${\displaystyle |E(C)|}$ divided by the minimum of the number of edges directed clockwise and the number of edges directed counterclockwise. Define the imbalance of the oriented graph to be the maximum imbalance of a cycle. Now, ${\displaystyle \chi _{c}(G)}$ is the minimum imbalance of an orientation of ${\displaystyle G}$.

The chromatic number of the flower snark J₅ is 3, but the circular chromatic number is ≤ 5/2.

It is relatively easy to see that ${\displaystyle \chi _{c}(G)\leq \chi (G)}$ (especially using 1 or 2), but in fact ${\displaystyle \lceil \chi _{c}(G)\rceil =\chi (G)}$. It is in this sense that we view circular chromatic number as a refinement of the usual chromatic number.

Circular coloring was originally defined by Vince (1988), who called it "star coloring".

Coloring is dual to the subject of nowhere-zero flows and indeed, circular coloring has a natural dual notion: circular flows.

Circular complete graphs

Circular complete graph
Vertices	n
Edges	n(n − 2k + 1) / 2
Girth	${\displaystyle \left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{otherwise}}\end{array}}\right.}$
Chromatic number	⌈n/k⌉
Properties	(n − 2k + 1)-regular Vertex-transitive Circulant Hamiltonian
Notation	${\displaystyle K_{n/k}}$
Table of graphs and parameters

For integers ${\displaystyle n,k}$ such that ${\displaystyle n\geq 2k}$, the circular complete graph ${\displaystyle K_{n/k}}$ (also known as a circular clique) is the graph with vertex set ${\displaystyle \mathbb {Z} /n\mathbb {Z} =\{0,1,\ldots ,n-1\}}$ and edges between elements at distance ${\displaystyle \geq k.}$ That is vertex i is adjacent to:

${\displaystyle i+k,i+k+1,\ldots ,i+n-k{\bmod {n}}.}$

${\displaystyle K_{n/1}}$ is just the complete graph K_n, while ${\displaystyle K_{2n+1/n}}$ is isomorphic to the cycle graph ${\displaystyle 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 ${\displaystyle K_{a/b}}$ admits a homomorphism into ${\displaystyle K_{c/d}}$ if and only if ${\displaystyle {\tfrac {a}{b}}\leq {\tfrac {c}{d}}.}$ This justifies the notation, since if ${\displaystyle {\tfrac {a}{b}}={\tfrac {c}{d}}}$ then ${\displaystyle K_{a/b}}$ and ${\displaystyle 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 ${\displaystyle \geq 2}$. For example

${\displaystyle K_{2/1}\to K_{5/2}\to K_{7/3}\to \cdots \to K_{3/1}\to K_{4/1}\to \cdots }$

or equivalently

${\displaystyle K_{2}\to C_{5}\to C_{7}\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 J₅ into K_5/2 ≈ C₅, which comes earlier than ${\displaystyle K_{3}}$ corresponding to the fact that ${\displaystyle \chi _{c}(J_{5})\leq 2.5<3.}$

See also

• Rank coloring

References

• Nadolski, Adam (2004), "Circular coloring of graphs", Graph colorings, Contemp. Math., 352, Providence, RI: Amer. Math. Soc., pp. 123–137, doi:10.1090/conm/352/09, MR 2076994.
• Vince, A. (1988), "Star chromatic number", Journal of Graph Theory, 12 (4): 551–559, doi:10.1002/jgt.3190120411, MR 0968751.
• Zhu, X. (2001), "Circular chromatic number, a survey", Discrete Mathematics, 229 (1–3): 371–410, doi:10.1016/S0012-365X(00)00217-X, MR 1815614.