# Definition:Coloring/Edge Coloring

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

- Definition:Undirected Network: 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.

- proper coloring, in which adjacent 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.