Editing Graph coloring (section)

=== Bounds on the chromatic index ===
An edge coloring of ''G'' is a vertex coloring of its [[line graph]] <math>L(G)</math>, and vice versa. Thus,
: <math>\chi'(G)=\chi(L(G)). </math>

There is a strong relationship between edge colorability and the graph's maximum degree <math>\Delta(G)</math>. Since all edges incident to the same vertex need their own color, we have
: <math>\chi'(G) \ge \Delta(G).</math>

Moreover,
: '''[[Kőnig's theorem (graph theory)|Kőnig's theorem]]:''' <math>\chi'(G) = \Delta(G)</math> if ''G'' is bipartite.

In general, the relationship is even stronger than what Brooks's theorem gives for vertex coloring:
: '''[[Vizing's theorem|Vizing's Theorem:]]''' A graph of maximal degree <math>\Delta</math> has edge-chromatic number <math>\Delta</math> or <math>\Delta+1</math>.