Home > Edge coloring

Here, "incident" means sharing a common endvertex. A proper edge coloring with k colors is called a (proper) k-edge-coloring and is equivalent to the problem of partitioning the edge set into k matchings. A graph that can be assigned a (proper) k-edge-coloring is k-edge-colorable.

The least number of colors needed in a (proper) edge coloring of a graph G is the chromatic index, or edge chromatic number, χ′(G). A graph is k-edge-chromatic if its chromatic index is exactly k.

Some properties of χ′(G):

1. χ′(G) = 1 if and only if G is a matching.
2. χ′(G) ≥ Δ(G).
3. χ′(G) ≤ Δ(G) + 1. (Vizing's theorem)
4. χ′(G) ≤ Δ(G) + μ(G), where G is allowed to be a multigraph.
5. χ′(G) = Δ(G) if G is a bipartite graph. (König's bipartite theorem)
6. χ′(G) = Δ(G) if G is simple, planar and Δ(G) ≥ 8. (Vizing 1965)

Here Δ(G) is the maximum degree; and μ(G), the multiplicity.

As we can see from above, χ′(G) equals either Δ(G) or Δ(G) + 1. When χ′(G) = Δ(G), G is said to be Class 1; otherwise, Class 2. Holyer (1981) proved that it is NP-complete to determine whether a simple graph is Class 1 or Class 2. Some efforts have been made to give a paritial characterization. For example, Vizing (1965) detemined a simple, planar graph is Class 1 if its maximum degree is at least 8. When the maximum degree is at most 5, it is known that some simple, planar graphs are Class 2. The remaining cases are still unsolved and can be summarized as follows:

Vizing's planar graph conjecture. (Vizing 1965)

All simple, planar graphs with maximum degree 6 or 7 are Class 1.

This conjecture has implication in the total coloring conjecture.

References

• Holyer, Ian (1981). The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720.
• Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. BooksEnthsiast.com.
• König, D. (1916). Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77, 453–465.
• Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3, 25–30.
• Vizing, V. G. (1965). Critical graphs with given chromatic class (in Russian). Metody Diskret. Analiz. 5, 9–17.