
In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, circular coloring is a kind of coloring that may be viewed as a refinement of the usual
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 o ...
. 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).
#
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.
#
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.
#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.
Circular coloring was originally defined by , who called it "star coloring".
Coloring is dual to the subject of
nowhere-zero flows In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs.
Definitions
Let ''G'' = (''V'',''E'') be a digraph and let ''M'' be an abelian group. A ...
and indeed, circular coloring has a natural dual notion: circular flows.
Circular complete graphs
For integers
such that
, the circular complete graph
(also known as a circular clique) is the graph with vertex set
and edges between elements at distance
That is vertex ''i'' is adjacent to:
:
is just the
complete graph , while
is the
cycle graph
A circular coloring is then, according to the second definition above, a
homomorphism
In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
into a circular complete graph. The crucial fact about these graphs is that
admits a homomorphism into
if and only if
This justifies the notation, since if
then
and
are homomorphically equivalent. Moreover, the homomorphism order among them refines the order given by complete graphs into a
dense order In mathematics, a partial order or total order < on a is said to be dense if, for all , corresponding to rational numbers
. For example
:
or equivalently
:
The example on the figure can be interpreted as a homomorphism from the
flower snark
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.
As snarks, the flower snarks are connected, bridgeless cubic graphs with chromatic index equal to 4. The flower ...
into , which comes earlier than
corresponding to the fact that
See also
*
Rank coloring
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi . Intuitively, this concept measures how close a
digraph is to a directed acyclic graph (DAG), in the sense that a DAG has
...
References
*.
*.
*.
Graph coloring
Parametric families of graphs
Regular graphs
{{combin-stub