Edge coloring
In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident 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 the edges of a given graph using at most different colors, for a given value of, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph.
By Vizing's theorem, the number of colors needed to edge color a simple graph is either its maximum degree or. For some graphs, such as bipartite graphs and high-degree planar graphs, the number of colors is always, and for multigraphs, the number of colors may be as large as. There are polynomial time algorithms that construct optimal colorings of bipartite graphs, and colorings of non-bipartite simple graphs that use at most colors; however, the general problem of finding an optimal edge coloring is NP-hard and the fastest known algorithms for it take exponential time. Many variations of the edge-coloring problem, in which an assignments of colors to edges must satisfy other conditions than non-adjacency, have been studied. Edge colorings have applications in scheduling problems and in frequency assignment for fiber optic networks.
Examples
A cycle graph may have its edges colored with two colors if the length of the cycle is even: simply alternate the two colors around the cycle. However, if the length is odd, three colors are needed.A complete graph with vertices is edge-colorable with colors when is an even number; this is a special case of Baranyai's theorem. provides the following geometric construction of a coloring in this case: place points at the vertices and center of a regular -sided polygon. For each color class, include one edge from the center to one of the polygon vertices, and all of the perpendicular edges connecting pairs of polygon vertices. However, when is odd, colors are needed: each color can only be used for edges, a fraction of the total.
Several authors have studied edge colorings of the odd graphs, -regular graphs in which the vertices represent teams of players selected from a pool of players, and in which the edges represent possible pairings of these teams. The case that gives the well-known Petersen graph. As explains the problem, the players wish to find a schedule for these pairings such that each team plays each of its six games on different days of the week, with Sundays off for all teams; that is, formalizing the problem mathematically, they wish to find a 6-edge-coloring of the 6-regular odd graph. When is 3, 4, or 8, an edge coloring of requires colors, but when it is 5, 6, or 7, only colors are needed.
Definitions
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, two distinct edges are considered to be adjacent when they share a common vertex. An edge coloring of a graph may also be thought of as equivalent to a vertex coloring of the line graph, the graph that has a vertex for every edge of and an edge for every pair of adjacent edges in.A proper edge coloring with different colors is called a -edge-coloring. A graph that can be assigned a -edge-coloring is said to be -edge-colorable. The smallest number of colors needed in a edge coloring of a graph is the chromatic index, or edge chromatic number,. The chromatic index is also sometimes written using the notation ; in this notation, the subscript one indicates that edges are one-dimensional objects. A graph is -edge-chromatic if its chromatic index is exactly. The chromatic index should not be confused with the chromatic number or, the minimum number of colors needed in a proper vertex coloring of .
Unless stated otherwise all graphs are assumed to be simple, in contrast to multigraphs in which two or more edges may be connecting the same pair of endpoints and in which there may be self-loops. For many problems in edge coloring, simple graphs behave differently from multigraphs, and additional care is needed to extend theorems about edge colorings of simple graphs to the multigraph case.
Relation to matching
A matching in a graph 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 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 different colors. For instance, the 16-vertex planar graph shown in the illustration has 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. 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 that does not have a perfect matching, this lower bound can be used to show that at least colors are needed. In particular, this is true for a regular graph with an odd number of vertices ; for such graphs, by the handshaking lemma, must itself be even. However, the inequality 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 and with edges in its perfect matchings, but it does not have a 3-edge-coloring.
Relation to degree
Vizing's theorem
The edge chromatic number of a graph is very closely related to the maximum degree, the largest number of edges incident to any single vertex of. Clearly,, for if different edges all meet at the same vertex, then all of these edges need to be assigned different colors from each other, and that can only be possible if there are at least colors available to be assigned. Vizing's theorem states that this bound is almost tight: for any graph, the edge chromatic number is either or.When, G is said to be of class 1; otherwise, it is said to be of class 2.
Every bipartite graph is of class 1, and almost all random graphs are of class 1. However, it is NP-complete to determine whether an arbitrary graph is of class 1.
proved that planar graphs of maximum degree at least eight are of class one and conjectured that the same is true for planar graphs of maximum degree seven or six. On the other hand, there exist planar graphs of maximum degree ranging from two through five that are of class two. The conjecture has since been proven for graphs of maximum degree seven. Bridgeless planar cubic graphs are all of class 1; this is an equivalent form of the four color theorem.
Regular graphs
A 1-factorization of a k-regular graph, a partition of the edges of the graph into perfect matchings, is the same thing as a k-edge-coloring of the graph. That is, a regular graph has a 1-factorization if and only if it is of class 1. As a special case of this, a 3-edge-coloring of a cubic graph is sometimes called a Tait coloring.Not every regular graph has a 1-factorization; for instance, the Petersen graph does not. More generally the snarks are defined as the graphs that, like the Petersen graph, are bridgeless, 3-regular, and of class 2.
According to the theorem of, every bipartite regular graph has a 1-factorization. The theorem was stated earlier in terms of projective configurations and was proven by Ernst Steinitz.
Multigraphs
For multigraphs, in which multiple parallel edges may connect the same two vertices, results that are similar to but weaker than Vizing's theorem are known relating the edge chromatic number , the maximum degree, and the multiplicity, the maximum number of edges in any bundle of parallel edges. As a simple example showing that Vizing's theorem does not generalize to multigraphs, consider a Shannon multigraph, a multigraph with three vertices and three bundles of parallel edges connecting each of the three pairs of vertices. In this example, but the edge chromatic number is . In a result that inspired Vizing, showed that this is the worst case: for any multigraph. Additionally, for any multigraph,, an inequality that reduces to Vizing's theorem in the case of simple graphs.Algorithms
Because the problem of testing whether a graph is class 1 is NP-complete, there is no known polynomial time algorithm for edge-coloring every graph with an optimal number of colors. Nevertheless, a number of algorithms have been developed that relax one or more of these criteria: they only work on a subset of graphs, or they do not always use an optimal number of colors, or they do not always run in polynomial time.Optimally coloring special classes of graphs
In the case of bipartite graphs or multigraphs with maximum degree, the optimal number of colors is exactly. showed that an optimal edge coloring of these graphs can be found in the near-linear time bound, where is the number of edges in the graph; simpler, but somewhat slower, algorithms are described by and. The algorithm of begins by making the input graph regular, without increasing its degree or significantly increasing its size, by merging pairs of vertices that belong to the same side of the bipartition and then adding a small number of additional vertices and edges. Then, if the degree is odd, Alon finds a single perfect matching in near-linear time, assigns it a color, and removes it from the graph, causing the degree to become even. Finally, Alon applies an observation of, that selecting alternating subsets of edges in an Euler tour of the graph partitions it into two regular subgraphs, to split the edge coloring problem into two smaller subproblems, and his algorithm solves the two subproblems recursively. The total time for his algorithm is.For planar graphs with maximum degree, the optimal number of colors is again exactly. With the stronger assumption that, it is possible to find an optimal edge coloring in linear time.
For d-regular graphs which are pseudo-random in the sense that their adjacency matrix has second largest eigenvalue at most, d is the optimal number of colors.