Edge coloring
In graph theory, edge coloring is one type of the graph coloring problem. A coloring of a graph's edges assigns a "color" to each edge of the graph. The objective is to color the graph's edges so that no vertex has two edges leaving it that have the same "color" and to use as few colors as possible. For example, the figure to the side shows a proper edge coloring, where no two edges out of the same vertex share the same color. In this example, the graph required three different colors, and could not be colored properly in any fewer.
Definition
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 . A graph is k-edge-chromatic if its chromatic index is exactly k.
Properties
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.
Classifying graphs and finding their chromatic index
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.
See also
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.