= Proper edge coloring
{title2=$e\ne f,\ e\cap f\ne\varnothing\Longrightarrow c(e)\ne c(f)$}
= Proper edge colouring
{synonym}
A <proper edge colouring> gives different labels to any two distinct <edges> sharing a <vertex>. We work with finite <undirected graphs> without <self-loops>; distinct parallel <edges> in a <multigraph> must also have different colours. For a <simple graph>, whose <edges> are two-element <sets>, the condition is
$$
e\ne f,\quad e\cap f\ne\varnothing\quad\Longrightarrow\quad c(e)\ne c(f).
$$
Every <colour class> $M_i=\{e\in E(G):c(e)=i\}$ is a <matching in a graph>. Conversely, a <set partition> of the <edges> into <matchings in a graph> supplies a <proper edge colouring>. Thus minimizing colours means grouping all the <edges> into as few <matchings in a graph> as possible.
The <line graph> makes the relationship with <proper vertex colouring> explicit: replace each original <edge> by a <vertex>, joining two new <vertices> exactly when their original <edges> share an endpoint. A <proper edge colouring> of $G$ becomes a <proper vertex colouring> of its <line graph> $L(G)$, so $\chi\prime(G)=\chi(L(G))$. For a <multigraph>, retain a distinct new <vertex> for each parallel <edge>.<Line graphs and edge coloring>[Line graphs and edge coloring, slide 1: line graph identity]{ref}
Back to article page
