Definition:Coloring
This page has been identified as a candidate for refactoring of medium complexity. In particular: Set up a disambiguation page so as to differentiate between this and the concept of the coloring of a partition of a set of integers in Ramsey theory Until this has been finished, please leave {{Refactor}} in the code.
New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code. |
.
Definition
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.
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.
Also see
- Definition:Proper Coloring: in which adjacent vertices or edges are required to have different colors.
Linguistic Note
The British English spelling of color and coloring is colour and colouring.
Why Colors?
It is clear that the nature of the actual elements of a coloring $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.