Editing Edge coloring (section)

==Relation to degree==

===Vizing's theorem===
{{Main|Vizing's theorem}}
The edge chromatic number of a graph {{mvar|G}} is very closely related to the [[Degree (graph theory)|maximum degree]] {{math|Δ(''G'')}}, the largest number of edges incident to any single vertex of {{mvar|G}}. Clearly, {{math|χ&prime;(''G'') ≥ Δ(''G'')}}, for if {{math|Δ}} different edges all meet at the same vertex {{mvar|v}}, then all of these edges need to be assigned different colors from each other, and that can only be possible if there are at least {{math|Δ}} colors available to be assigned. [[Vizing's theorem]] (named for [[Vadim G. Vizing]] who published it in 1964) states that this bound is almost tight: for any graph, the edge chromatic number is either {{math|Δ(''G'')}} or {{math|Δ(''G'') + 1}}.
When {{math|1=χ&prime;(''G'') = Δ(''G'')}}, ''G'' is said to be of class 1; otherwise, it is said to be of class 2.

Every bipartite graph is of class 1,<ref>{{harvtxt|Kőnig|1916}}</ref> and [[almost all]] [[random graph]]s are of class 1.<ref>{{harvtxt|Erdős|Wilson|1977}}.</ref> However, it is [[NP-complete]] to determine whether an arbitrary graph is of class 1.<ref>{{harvtxt|Holyer|1981}}.</ref>

{{harvtxt|Vizing|1965}} proved that [[planar graph]]s of maximum degree at least eight are of class one and conjectured that the same is true for planar graphs of maximum degree seven or six. On the other hand, there exist planar graphs of maximum degree ranging from two through five that are of class two. The conjecture has since been proven for graphs of maximum degree seven.<ref>{{harvtxt|Sanders|Zhao|2001}}.</ref> [[Bridge (graph theory)|Bridgeless]] planar [[cubic graph]]s are all of class 1; this is an equivalent form of the [[four color theorem]].<ref>{{harvtxt|Tait|1880}}; {{harvtxt|Appel|Haken|1976}}.</ref>

===Regular graphs===
A [[1-factorization]] of a ''k''-[[regular graph]], a partition of the edges of the graph into [[perfect matching]]s, is the same thing as a ''k''-edge-coloring of the graph. That is, a regular graph has a 1-factorization if and only if it is of class 1.  As a special case of this, a 3-edge-coloring of a [[cubic graph|cubic]] (3-regular) graph is sometimes called a '''Tait coloring'''.

Not every regular graph has a 1-factorization; for instance, the [[Petersen graph]] does not. More generally the [[Snark (graph theory)|snark]]s are defined as the graphs that, like the Petersen graph, are bridgeless, 3-regular, and of class 2.

According to the theorem of {{harvtxt|Kőnig|1916}}, every bipartite regular graph has a 1-factorization. The theorem was stated earlier in terms of [[projective configuration]]s and was proven by [[Ernst Steinitz]].

===Multigraphs===
[[File:Multigraph-edge-coloring.svg|thumb|A [[Shannon multigraph]] with degree six and edge multiplicity three, requiring nine colors in any edge coloring]]
For [[multigraph]]s, in which multiple parallel edges may connect the same two vertices, results that are similar to but weaker than Vizing's theorem are known relating the edge chromatic number  {{math|1=χ&prime;(''G'')}}, the maximum degree {{math|Δ(''G'')}}, and the multiplicity {{math|μ(''G'')}}, the maximum number of edges in any bundle of parallel edges. As a simple example showing that Vizing's theorem does not generalize to multigraphs, consider a [[Shannon multigraph]], a multigraph with three vertices and three bundles of {{math|μ(''G'')}} parallel edges connecting each of the three pairs of vertices. In this example, {{math|1=Δ(''G'') = 2μ(''G'')}} (each vertex is incident to only two out of the three bundles of {{math|μ(''G'')}} parallel edges) but the edge chromatic number is {{math|3μ(''G'')}} (there are {{math|3μ(''G'')}} edges in total, and every two edges are adjacent, so all edges must be assigned different colors to each other). In a result that inspired Vizing,<ref>{{harvtxt|Soifer|2008}}, p. 136.</ref> {{harvtxt|Shannon|1949}} showed that this is the worst case: {{math|χ&prime;(''G'') ≤ (3/2)Δ(''G'')}} for any multigraph {{mvar|G}}. Additionally, for any multigraph {{mvar|G}}, {{math|χ&prime;(''G'') ≤ Δ(''G'') + μ(''G'')}}, an inequality that reduces to Vizing's theorem in the case of simple graphs (for which {{math|1=μ(''G'') = 1}}).