Definition:Coloring
Contents |
Vertex Coloring
A vertex $k$-coloring of a simple graph $G = \left({V, E}\right)$ is defined as an assignment of one element from a set $C$ of $k$ colors to each vertex in $V$.
That is, a vertex $k$-coloring of the graph $G = \left({V, E}\right)$ is a mapping $c: V \to \left\{{1, 2, \ldots k}\right\}$.
A graph with such a coloring is called a vertex-colored graph.
Comparison with Labeled Graph
It can be seen that a vertex-colored graph can be considered as a labeled graph in which the labels are considered as colors.
Edge Coloring
An edge $k$-coloring of a simple graph $G = \left({V, E}\right)$ is defined as an assignment of one element from a set $C$ of $k$ colors to each edge in $E$.
That is, an edge $k$-coloring of the graph $G = \left({V, E}\right)$ is a mapping $c: E \to \left\{{1, 2, \ldots k}\right\}$.
A graph with such a coloring is called an edge-colored graph.
Comparison with Undirected Network
It can be seen that an edge-colored graph can be considered as an undirected network in which the colors correspond to numbers.
However, in an edge-colored graph, the actual values of the numbers is unimportant.
Also see
Compare with the concept of a proper coloring, in which adjacent vertices or edges are required to have different colors.
Linguistic Note
The UK english spelling of color is colour.
Why Colors?
It is clear that the nature of the actual elements of $C$ is irrelevant. They are traditionally referred to as "colors" because this subfield of graph theory arose from considerations of the coloring of the faces of planar graphs such that adjacent faces have different colors.
This was the origin of the famous Four Color Theorem.
