Definition:Proper Coloring

Definition

Proper Vertex Coloring

A proper (vertex) $k$-coloring of a simple graph $G = \left({V, E}\right)$ 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 $k$-coloring of the graph $G = \left({V, E}\right)$ is a mapping $c: V \to \left\{{1, 2, \ldots k}\right\}$ such that:

$\forall e = \left\{{u, v}\right\} \in E: c \left({u}\right) \ne \left({v}\right)$

Proper Edge Coloring

A proper (edge) $k$-coloring of a simple graph $G = \left({V, E}\right)$ is defined as an edge coloring from a set of $k$ colors such that no two adjacent edges share a common color.

That is, a $k$-coloring of the graph $G = \left({V, E}\right)$ is a mapping $c: E \to \left\{{1, 2, \ldots k}\right\}$ such that:

$\forall v \in V: \forall e = \left\{{u_k, v}\right\} \in E: c \left\{{u_i, v}\right\} \ne c \left\{{u_j, v}\right\}$