Edge coloring

3-edge-coloring of Desargues graph.

In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring.

The edge-coloring problem asks whether it is possible to color a given graph using at most n colors. The minimum required number of colors for a graph is called the chromatic index. For example, the graph on the right can be colored by three colors but cannot be colored by two colors, and thus has chromatic index three.

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 χ₁(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).

Properties

In the following, let Δ(G) denote the maximum degree; and μ(G), the multiplicity. Some properties of χ′(G):

1. χ′(G) = 1 if and only if G is a matching.
2. χ′(G) ≥ Δ(G).
3. χ′(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).
4. χ′(G) ≤ Δ(G) + μ(G), where G is allowed to be a multigraph.
5. χ′(G) ≤ (3/2)Δ(G) for any multigraph (Shannon 1949)
6. χ′(G) = Δ(G) if G is a bipartite graph. (König's bipartite theorem)
7. χ′(G) = Δ(G) if G is simple, planar and Δ(G) ≥ 7. (Vizing 1965 combined with Sanders & Zhao 2001)
8. χ′(G) = Δ(G) for almost all graphs (Erdős & Wilson 1977).

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.

See also

• Thue number

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:10.1016/0095-8956(77)90039-9, 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:10.1137/0210055 .
• 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:10.1007/BF01456961 .
• 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:10.1006/jctb.2001.2047 .
• 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.)

External links

• Proof of Vizing's theorem at PlanetMath.