Edge Coloring - Relation To Matching

Relation To Matching

A matching in a graph G is a set of edges, no two of which are adjacent; a perfect matching is a matching that includes edges touching all of the vertices of the graph, and a maximum matching is a matching that includes as many edges as possible. In an edge coloring, the set of edges with any one color must all be non-adjacent to each other, so they form a matching. That is, a proper edge coloring is the same thing as a partition of the graph into disjoint matchings.

If the size of a maximum matching in a given graph is small, then many matchings will be needed in order to cover all of the edges of the graph. Expressed more formally, this reasoning implies that if a graph has m edges in total, and if at most β edges may belong to a maximum matching, then every edge coloring of the graph must use at least m/β different colors. For instance, the 16-vertex planar graph shown in the illustration has m = 24 edges. In this graph, there can be no perfect matching; for, if the center vertex is matched, the remaining unmatched vertices may be grouped into three different connected components with four, five, and five vertices, and the components with an odd number of vertices cannot be perfectly matched. However, the graph has maximum matchings with seven edges, so β = 7. Therefore, the number of colors needed to edge-color the graph is at least 24/7, and since the number of colors must be an integer it is at least four.

For a regular graph of degree k that does not have a perfect matching, this lower bound can be used to show that at least k + 1 colors are needed. In particular, this is true for a regular graph with an odd number of vertices (such as the odd complete graphs); for such graphs, by the handshaking lemma, k must itself be even. However, the inequality χ′ ≥ m/β does not fully explain the chromatic index of every regular graph, because there are regular graphs that do have perfect matchings but that are not k-edge-colorable. For instance, the Petersen graph is regular, with m = 15 and with β = 5 edges in its perfect matchings, but it does not have a 3-edge-coloring.