Edge coloring
From Wikipedia, the free encyclopedia
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; we say the chromatic index of the graph is 3.
Contents |
[edit] 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 χ1(G). A graph is k-edge-chromatic if its chromatic index is exactly k. The chromatic index should not be confused with the chromatic number χ(G).
[edit] Properties
Some properties of χ′(G):
- χ′(G) = 1 if and only if G is a matching.
- χ′(G) ≥ Δ(G).
- χ′(G) ≤ Δ(G) + 1. (Vizing's theorem, named for Vadim G. Vizing who discovered it in 1964, divides all graphs into 2 classes: Class 1 graphs have χ′(G) = Δ; Class 2 graphs have χ′(G) ≤ Δ(G)+1).
- χ′(G) ≤ Δ(G) + μ(G), where G is allowed to be a multigraph.
- χ′(G) ≤ (3/2)Δ(G) for any multigraph (Shannon 1949)
- χ′(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 & Zhao 2001)
- χ′(G) = Δ(G) for almost all graphs (Erdős & Wilson 1977).
Here Δ(G) is the maximum degree; and μ(G), the multiplicity.
[edit] 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.
Sanders & Zhao (2001) 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
[edit] References
- Erdős, Paul; Wilson, Robin J. (1977), "Note on the chromatic index of almost all graphs", Journal of Combinatorial Theory, Series B 23: 255–257, doi:, http://www.renyi.hu/~p_erdos/1977-20.pdf.
- Holyer, Ian (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing 10: 718–720, doi:.
- 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, doi:.
- Sanders, Daniel P.; Zhao, Yue (2001), "Planar graphs of maximum degree seven are class I", Journal of Combinatorial Theory, Series B 83 (2): 201–212, doi:.
- Shannon, Claude E. (1949), "A theorem on coloring the lines of a network", J. Math. Physics 28: 148–151, MR0030203.
- Vizing, V. G. (1964), "On an estimate of the chromatic class of a p-graph", Diskret. Analiz. 3: 25–30, MR0180505.
- Vizing, V. G. (1965), "Critical graphs with given chromatic class", Metody Diskret. Analiz. 5: 9–17. (In Russian.)
