Edge coloring

From Wikipedia, the free encyclopedia

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

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 $χ 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) ≥ 7. (Vizing 1965 combined with Sanders and Zhao 2001)

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. However, efforts have been made to give a partial characterization. For example, Vizing (1965) showed that a simple, planar graph is Class 1 if its maximum degree is at least 8. In contrast, he observed that for maximum degree 2, 3, 4, and 5, there exist simple, planar graphs of Class 2. For example, begin with a platonic solid and replace a single edge by a path of two adjacent edges. In this way, the platonic solids yield simple, planar class 2 graphs of maximum degree 3, 4, and 5. (Every cycle of odd length is a class 2 graph of maximum degree 2.) Vizing conjectured the following result for the two cases he did not solve:

Vizing's planar graph conjecture. (Vizing 1965)

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

In 2001, Sanders and Zhao partially proved Vizing's planar graph conjecture. They showed that all simple, planar graphs with maximum degree 7 are class 1. Thus, the only case that remains unsolved for simple, planar graphs is maximum degree 6.

This conjecture has implications for the total coloring conjecture.

[edit] See also

Thue number

[edit] 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.
Sanders, Daniel P.; Zhao, Yue (2001). Planar Graphs of Maximum Degree Seven are Class I. Journal of Combinatorial Theory, Series B. 83, Issue 2, 201–212.
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.