Definition:Proper Coloring/Vertex Coloring

From ProofWiki
Jump to navigation Jump to search


Let $G = \struct {V, E}$ be a simple graph.

A proper (vertex) $k$-coloring of $G$ is defined as a vertex coloring from a set of $k$ colors such that no two adjacent vertices share a common color.

That is, a proper $k$-coloring of $G$ is a mapping $c: V \to \set {1, 2, \ldots k}$ such that:

$\forall e = \set {u, v} \in E: \map c u \ne \map c v$

Also see