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.
Read more about this topic: Edge Coloring
Famous quotes containing the words relation to and/or relation:
“Much poetry seems to be aware of its situation in time and of its relation to the metronome, the clock, and the calendar. ... The season or month is there to be felt; the day is there to be seized. Poems beginning “When” are much more numerous than those beginning “Where” of “If.” As the meter is running, the recurrent message tapped out by the passing of measured time is mortality.”
—William Harmon (b. 1938)
“To criticize is to appreciate, to appropriate, to take intellectual possession, to establish in fine a relation with the criticized thing and to make it one’s own.”
—Henry James (1843–1916)