TOPICS
Search

Circular Chromatic Number


The circular chromatic number chi_c(G) of a finite simple graph G containing an graph edge is the infimum of the real numbers r>=2 for which its vertices can be mapped to a circle of circumference r so that adjacent vertices have circular distance at least 1. An edgeless nonempty graph has chi_c(G)=1 (Vince 1988, Zhu 2001). Circular distance is the length of the shorter arc between the two points.

This refines the chromatic number, since chi(G)-1<chi_c(G)<=chi(G). The signed circular chromatic number extends the definition by allowing positive and negative edges to impose different distance constraints.


See also

Chromatic Number, Signed Circular Chromatic Number

Explore with Wolfram|Alpha

References

Vince, A. "Star Chromatic Number." J. Graph Th. 12, 551-559, 1988. https://doi.org/10.1002/jgt.3190120411.Zhu, X. "Circular Chromatic Number: A Survey." Disc. Math. 229, 371-410, 2001. https://doi.org/10.1016/S0012-365X(00)00217-X.

Cite this as:

Weisstein, Eric W. "Circular Chromatic Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CircularChromaticNumber.html

Subject classifications