Edge coloring

Encyclopedia : E : ED : EDG : Edge coloring

In graph theory, as with its vertex counterpart, an edge coloring of a graph, when mentioned without any qualification, is always assumed to be a proper coloring of the edges, meaning no two adjacent edges are assigned the same color. Here, "adjacent" means sharing a common vertex. 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. A 3-edge-coloring of a cubic graph is sometimes called a Tait coloring.

The smallest number of colors needed in a (proper) edge coloring of a graph G is the chromatic index, or edge chromatic number, χ′(G), also sometimes notated [\chi_1(G)]. A graph is k-edge-chromatic if its chromatic index is exactly k.

Some properties of χ′(G):

χ′(G) = 1 if and only if G is a matching.
χ′(G) ≥ Δ(G).
χ′(G) ≤ Δ(G) + 1. (Vizing's theorem)
χ′(G) ≤ Δ(G) + μ(G), where G is allowed to be a multigraph.
χ′(G) = Δ(G) if G is a bipartite graph. (König's bipartite theorem)
χ′(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 partial characterization. For example, Vizing (1965) determined that 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 implications for 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. ISBN 0-471-02865-7.
König, D. (1916). Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen 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.

External links

[Proof of Vizing's theorem] at PlanetMath.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.