Circular coloring
Encyclopedia
In graph theory
, circular coloring may be viewed as a refinement of usual graph coloring
. The circular chromatic number of a graph
, denoted 
can be given by any of the following definitions, all of which are equivalent (for finite graphs).
1.
is the infimum over all real numbers 
so that there exists a map from 
to a circle of circumference 1 with the property that any two adjacent vertices map to points at distance 
along this circle.
2.
is the infimum over all rational numbers 
so that there exists a map from 
to the cyclic group 
with the property that adjacent vertices map to elements at distance 
apart.
3. In an oriented graph, declare the imbalance of a cycle
to be 
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, 
is the minimum imbalance of an orientation of 
.
It is relatively easy to see that
(especially using 1. or 2.), but in fact 
. It is in this sense that we view circular chromatic number as a refinement of the usual chromatic number.
Coloring is dual to the subject of nowhere-zero flows
and indeed, circular coloring has a natural dual notion: circular flows.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, circular coloring may be viewed as a refinement of usual graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
. The circular chromatic number of a graph
, denoted can be given by any of the following definitions, all of which are equivalent (for finite graphs).1.
is the infimum over all real numbers so that there exists a map from to a circle of circumference 1 with the property that any two adjacent vertices map to points at distance along this circle.2.
is the infimum over all rational numbers so that there exists a map from to the cyclic group with the property that adjacent vertices map to elements at distance apart.3. In an oriented graph, declare the imbalance of a cycle
to be 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, is the minimum imbalance of an orientation of .It is relatively easy to see that
(especially using 1. or 2.), but in fact . It is in this sense that we view circular chromatic number as a refinement of the usual chromatic number.Coloring is dual to the subject of nowhere-zero flows
Nowhere-zero flows
In graph theory, nowhere-zero flows are a special type of network flow which is related to coloring planar graphs. Let G = be a directed graph and let M be an abelian group...
and indeed, circular coloring has a natural dual notion: circular flows.