Definition:Proper Coloring/Edge Coloring

Definition

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

A proper (edge) $k$-coloring of $G$ 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 proper $k$-coloring of $G$ is a mapping $c: E \to \set {1, 2, \ldots k}$ such that:

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

Also see

• Definition:Proper Vertex Coloring