# Definition:Coloring

.

## Contents

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