Edge Coloring

Definition (Edge Coloring)

An edge coloring of a graph $G$ is an assignment of a color to each edge so that no two edges that share the same vertex share the same color.

For example, if we want to color Complete Graph $K_4$,

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

with $\text{red},\text{green},$ and $\text{orange}$.

Definition (Edge Chromatic Number)

We can find the Edge Chromatic Number,

$${\chi }^{\prime }(G):=\text{minimum number of colors to find an edge coloring of }G$$

Related: Definition (Chromatic Number).

It is not hard to see that

$${\chi }^{\prime }(G)=\chi (L(G))$$

where $L(G)$ is the line graph of the graph $G$.

Edge Chromatic Number Bounds

From corollary, we have

$$\chi (L(G))\ge \omega (L(G))$$

maximally, if $G$ is a starfish graph, it’s line graph is a complete graph. This gives us another (albeit weaker) lower bound:

$$\chi (L(G))\ge \omega (L(G))\ge \Delta (G)$$

For an upper bound, from lemma,

$${\chi }^{\prime }(G)=\chi (L(G))\le \Delta (L(G))+1$$

What is the degree of some vertex in the line graph?

Suppose we had some edge $e$ connecting two starfishes centered on $u,v$. Then

$${\mathrm{deg}}_{L(G)}(e)={\mathrm{deg}}_G(u)-1+{\mathrm{deg}}_G(v)-1={\mathrm{deg}}_G(u)+{\mathrm{deg}}_G(v)-2\le 2\Delta (G)-2$$

which gives us:

$${\chi }^{\prime }(G)=\chi (L(G))\le \Delta (L(G))+1\le 2(\Delta (G)-1)$$

See Vizing’s Theorem.