|
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 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. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three. 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-complete 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.〔, problem 16.4, p. 133.〕 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.〔, problem 16.5, p. 133. The fact that either or colors are needed is an instance of Vizing's theorem.〕 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 (with one player left as "odd man out" to referee the game). The case that gives the well-known Petersen graph. As explains the problem (for ), 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.〔; ; .〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Edge coloring」の詳細全文を読む スポンサード リンク
|