# Definition:Coloring/Edge Coloring

(Redirected from Definition:Edge Coloring)
Jump to navigation Jump to search

## Definition

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

However, in an edge-colored graph, the actual values of the numbers is unimportant.

## 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.