Edge coloring
|
|
In graph theory, similar to its vertex counterpart, an edge coloring of a graph, when used without any qualification, is always assumed to be a proper coloring on the edges, meaning no two adjacent edges are assigned the same color. Here, "adjacent" 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 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 <math>\chi_1(G)<math>. 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 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. 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.