# Definition:Coloring/Vertex Coloring

## Definition

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

## Also see

- Definition:Labeled Graph: a vertex-colored graph can be considered as a labeled graph in which the labels are considered as colors.

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