Edge coloring

From Wikipedia for FEVERv2
(Redirected from Chromatic index)
Jump to navigation Jump to search

In graph theory, an 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. Edge coloring_sentence_0

For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge coloring_sentence_1

Edge colorings are one of several different types of graph coloring. Edge coloring_sentence_2

The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. Edge coloring_sentence_3

The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. Edge coloring_sentence_4

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. Edge coloring_sentence_5

By Vizing's theorem, the number of colors needed to edge color a simple graph is either its maximum degree Δ or Δ+1. Edge coloring_sentence_6

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 3Δ/2. Edge coloring_sentence_7

There are polynomial time algorithms that construct optimal colorings of bipartite graphs, and colorings of non-bipartite simple graphs that use at most Δ+1 colors; however, the general problem of finding an optimal edge coloring is NP-hard and the fastest known algorithms for it take exponential time. Edge coloring_sentence_8

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 coloring_sentence_9

Edge colorings have applications in scheduling problems and in frequency assignment for fiber optic networks. Edge coloring_sentence_10

Examples Edge coloring_section_0

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. Edge coloring_sentence_11

However, if the length is odd, three colors are needed. Edge coloring_sentence_12

A complete graph Kn with n vertices is edge-colorable with n − 1 colors when n is an even number; this is a special case of Baranyai's theorem. Edge coloring_sentence_13

provides the following geometric construction of a coloring in this case: place n points at the vertices and center of a regular (n − 1)-sided polygon. Edge coloring_sentence_14

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. Edge coloring_sentence_15

However, when n is odd, n colors are needed: each color can only be used for (n − 1)/2 edges, a 1/n fraction of the total. Edge coloring_sentence_16

Several authors have studied edge colorings of the odd graphs, n-regular graphs in which the vertices represent teams of n − 1 players selected from a pool of 2n − 1 players, and in which the edges represent possible pairings of these teams (with one player left as "odd man out" to referee the game). Edge coloring_sentence_17

The case that n = 3 gives the well-known Petersen graph. Edge coloring_sentence_18

As explains the problem (for n = 6), 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 O6. Edge coloring_sentence_19

When n is 3, 4, or 8, an edge coloring of On requires n + 1 colors, but when it is 5, 6, or 7, only n colors are needed. Edge coloring_sentence_20

Definitions Edge coloring_section_1

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. Edge coloring_sentence_21

Here, two distinct edges are considered to be adjacent when they share a common vertex. Edge coloring_sentence_22

An edge coloring of a graph G may also be thought of as equivalent to a vertex coloring of the line graph L(G), the graph that has a vertex for every edge of G and an edge for every pair of adjacent edges in G. Edge coloring_sentence_23

A proper edge coloring with k different colors is called a (proper) k-edge-coloring. Edge coloring_sentence_24

A graph that can be assigned a k-edge-coloring is said to be k-edge-colorable. Edge coloring_sentence_25

The smallest number of colors needed in a (proper) edge coloring of a graph G is the chromatic index, or edge chromatic number, χ′(G). Edge coloring_sentence_26

The chromatic index is also sometimes written using the notation χ1(G); in this notation, the subscript one indicates that edges are one-dimensional objects. Edge coloring_sentence_27

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) or χ0(G), the minimum number of colors needed in a proper vertex coloring of G. Edge coloring_sentence_28

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. Edge coloring_sentence_29

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. Edge coloring_sentence_30

Relation to matching Edge coloring_section_2

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. Edge coloring_sentence_31

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. Edge coloring_sentence_32

That is, a proper edge coloring is the same thing as a partition of the graph into disjoint matchings. Edge coloring_sentence_33

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. Edge coloring_sentence_34

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. Edge coloring_sentence_35

For instance, the 16-vertex planar graph shown in the illustration has m = 24 edges. Edge coloring_sentence_36

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. Edge coloring_sentence_37

However, the graph has maximum matchings with seven edges, so β = 7. Edge coloring_sentence_38

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. Edge coloring_sentence_39

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. Edge coloring_sentence_40

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. Edge coloring_sentence_41

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. Edge coloring_sentence_42

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. Edge coloring_sentence_43

Relation to degree Edge coloring_section_3

Vizing's theorem Edge coloring_section_4

Main article: Vizing's theorem Edge coloring_sentence_44

The edge chromatic number of a graph G is very closely related to the maximum degree Δ(G), the largest number of edges incident to any single vertex of G. Clearly, χ′(G) ≥ Δ(G), for if Δ different edges all meet at the same vertex v, 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. Edge coloring_sentence_45

Vizing's theorem (named for Vadim G. Vizing who published it in 1964) states that this bound is almost tight: for any graph, the edge chromatic number is either Δ(G) or Δ(G) + 1. Edge coloring_sentence_46

When χ′(G) = Δ(G), G is said to be of class 1; otherwise, it is said to be of class 2. Edge coloring_sentence_47

Every bipartite graph is of class 1, and almost all random graphs are of class 1. Edge coloring_sentence_48

However, it is NP-complete to determine whether an arbitrary graph is of class 1. Edge coloring_sentence_49

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. Edge coloring_sentence_50

On the other hand, there exist planar graphs of maximum degree ranging from two through five that are of class two. Edge coloring_sentence_51

The conjecture has since been proven for graphs of maximum degree seven. Edge coloring_sentence_52

Bridgeless planar cubic graphs are all of class 1; this is an equivalent form of the four color theorem. Edge coloring_sentence_53

Regular graphs Edge coloring_section_5

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. Edge coloring_sentence_54

That is, a regular graph has a 1-factorization if and only if it is of class 1. Edge coloring_sentence_55

As a special case of this, a 3-edge-coloring of a cubic (3-regular) graph is sometimes called a Tait coloring. Edge coloring_sentence_56

Not every regular graph has a 1-factorization; for instance, the Petersen graph does not. Edge coloring_sentence_57

More generally the snarks are defined as the graphs that, like the Petersen graph, are bridgeless, 3-regular, and of class 2. Edge coloring_sentence_58

According to the theorem of , every bipartite regular graph has a 1-factorization. Edge coloring_sentence_59

The theorem was stated earlier in terms of projective configurations and was proven by Ernst Steinitz. Edge coloring_sentence_60

Multigraphs Edge coloring_section_6

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 χ′(G), the maximum degree Δ(G), and the multiplicity μ(G), the maximum number of edges in any bundle of parallel edges. Edge coloring_sentence_61

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 μ(G) parallel edges connecting each of the three pairs of vertices. Edge coloring_sentence_62

In this example, Δ(G) = 2μ(G) (each vertex is incident to only two out of the three bundles of μ(G) parallel edges) but the edge chromatic number is 3μ(G) (there are 3μ(G) edges in total, and every two edges are adjacent, so all edges must be assigned different colors to each other). Edge coloring_sentence_63

In a result that inspired Vizing, showed that this is the worst case: χ′(G) ≤ (3/2)Δ(G) for any multigraph G. Additionally, for any multigraph G, χ′(G) ≤ Δ(G) + μ(G), an inequality that reduces to Vizing's theorem in the case of simple graphs (for which μ(G) = 1). Edge coloring_sentence_64

Algorithms Edge coloring_section_7

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. Edge coloring_sentence_65

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. Edge coloring_sentence_66

Optimally coloring special classes of graphs Edge coloring_section_8

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 O(m log Δ), where m is the number of edges in the graph; simpler, but somewhat slower, algorithms are described by and . Edge coloring_sentence_67

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. Edge coloring_sentence_68

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. Edge coloring_sentence_69

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. Edge coloring_sentence_70

The total time for his algorithm is O(m log m). Edge coloring_sentence_71

For planar graphs with maximum degree Δ ≥ 7, the optimal number of colors is again exactly Δ. Edge coloring_sentence_72

With the stronger assumption that Δ ≥ 9, it is possible to find an optimal edge coloring in linear time (). Edge coloring_sentence_73

For d-regular graphs which are pseudo-random in the sense that their adjacency matrix has second largest eigenvalue (in absolute value) at most d, d is the optimal number of colors (). Edge coloring_sentence_74

Algorithms that use more than the optimal number of colors Edge coloring_section_9

and describe polynomial time algorithms for coloring any graph with Δ + 1 colors, meeting the bound given by Vizing's theorem; see Misra & Gries edge coloring algorithm. Edge coloring_sentence_75

A greedy coloring algorithm that considers the edges of a graph or multigraph one by one, assigning each edge the first available color, may sometimes use as many as 2Δ − 1 colors, which may be nearly twice as many number of colors as is necessary. Edge coloring_sentence_76

However, it has the advantage that it may be used in the online algorithm setting in which the input graph is not known in advance; in this setting, its competitive ratio is two, and this is optimal: no other online algorithm can achieve a better performance. Edge coloring_sentence_77

However, if edges arrive in a random order, and the input graph has a degree that is at least logarithmic, then smaller competitive ratios can be achieved. Edge coloring_sentence_78

Exact algorithms Edge coloring_section_10

It is straightforward to test whether a graph may be edge colored with one or two colors, so the first nontrivial case of edge coloring is testing whether a graph has a 3-edge-coloring. Edge coloring_sentence_79

As showed, it is possible to test whether a graph has a 3-edge-coloring in time O(1.344), while using only polynomial space. Edge coloring_sentence_80

Although this time bound is exponential, it is significantly faster than a brute force search over all possible assignments of colors to edges. Edge coloring_sentence_81

Every biconnected 3-regular graph with n vertices has O(2) 3-edge-colorings; all of which can be listed in time O(2) (somewhat slower than the time to find a single coloring); as Greg Kuperberg observed, the graph of a prism over an n/2-sided polygon has Ω(2) colorings (lower instead of upper bound), showing that this bound is tight. Edge coloring_sentence_82

By applying exact algorithms for vertex coloring to the line graph of the input graph, it is possible to optimally edge-color any graph with m edges, regardless of the number of colors needed, in time 2m and exponential space, or in time O(2.2461) and only polynomial space (). Edge coloring_sentence_83

Because edge coloring is NP-complete even for three colors, it is unlikely to be fixed parameter tractable when parametrized by the number of colors. Edge coloring_sentence_84

However, it is tractable for other parameters. Edge coloring_sentence_85

In particular, showed that for graphs of treewidth w, an optimal edge coloring can be computed in time O(nw(6w)), a bound that depends superexponentially on w but only linearly on the number n of vertices in the graph. Edge coloring_sentence_86

formulate the edge coloring problem as an integer program and describe their experience using an integer programming solver to edge color graphs. Edge coloring_sentence_87

However, they did not perform any complexity analysis of their algorithm. Edge coloring_sentence_88

Additional properties Edge coloring_section_11

A graph is uniquely k-edge-colorable if there is only one way of partitioning the edges into k color classes, ignoring the k! Edge coloring_sentence_89

possible permutations of the colors. Edge coloring_sentence_90

For k ≠ 3, the only uniquely k-edge-colorable graphs are paths, cycles, and stars, but for k = 3 other graphs may also be uniquely k-edge-colorable. Edge coloring_sentence_91

Every uniquely 3-edge-colorable graph has exactly three Hamiltonian cycles (formed by deleting one of the three color classes) but there exist 3-regular graphs that have three Hamiltonian cycles and are not uniquely 3-colorable, such as the generalized Petersen graphs G(6n + 3, 2) for n ≥ 2. Edge coloring_sentence_92

The only known nonplanar uniquely 3-colorable graph is the generalized Petersen graph G(9,2), and it has been conjectured that no others exist. Edge coloring_sentence_93

investigated the non-increasing sequences of numbers m1, m2, m3, ... with the property that there exists a proper edge coloring of a given graph G with m1 edges of the first color, m2 edges of the second color, etc. Edge coloring_sentence_94

They observed that, if a sequence P is feasible in this sense, and is greater in lexicographic order than a sequence Q with the same sum, then Q is also feasible. Edge coloring_sentence_95

For, if P > Q in lexicographic order, then P can be transformed into Q by a sequence of steps, each of which reduces one of the numbers mi by one unit and increases another later number mj with i < j by one unit. Edge coloring_sentence_96

In terms of edge colorings, starting from a coloring that realizes P, each of these same steps may be performed by swapping colors i and j on a Kempe chain, a maximal path of edges that alternate between the two colors. Edge coloring_sentence_97

In particular, any graph has an equitable edge coloring, an edge coloring with an optimal number of colors in which every two color classes differ in size by at most one unit. Edge coloring_sentence_98

The De Bruijn–Erdős theorem may be used to transfer many edge coloring properties of finite graphs to infinite graphs. Edge coloring_sentence_99

For instance, Shannon's and Vizing's theorems relating the degree of a graph to its chromatic index both generalize straightforwardly to infinite graphs. Edge coloring_sentence_100

considers the problem of finding a graph drawing of a given cubic graph with the properties that all of the edges in the drawing have one of three different slopes and that no two edges lie on the same line as each other. Edge coloring_sentence_101

If such a drawing exists, then clearly the slopes of the edges may be used as colors in a 3-edge-coloring of the graph. Edge coloring_sentence_102

For instance, the drawing of the utility graph K3,3 as the edges and long diagonals of a regular hexagon represents a 3-edge-coloring of the graph in this way. Edge coloring_sentence_103

As Richter shows, a 3-regular simple bipartite graph, with a given Tait coloring, has a drawing of this type that represents the given coloring if and only if the graph is 3-edge-connected. Edge coloring_sentence_104

For a non-bipartite graph, the condition is a little more complicated: a given coloring can be represented by a drawing if the bipartite double cover of the graph is 3-edge-connected, and if deleting any monochromatic pair of edges leads to a subgraph that is still non-bipartite. Edge coloring_sentence_105

These conditions may all be tested easily in polynomial time; however, the problem of testing whether a 4-edge-colored 4-regular graph has a drawing with edges of four slopes, representing the colors by slopes, is complete for the existential theory of the reals, a complexity class at least as difficult as being NP-complete. Edge coloring_sentence_106

Other types Edge coloring_section_12

The Thue number of a graph is the number of colors required in an edge coloring meeting the stronger requirement that, in every even-length path, the first and second halves of the path form different sequences of colors. Edge coloring_sentence_107

The arboricity of a graph is the minimum number of colors required so that the edges of each color have no cycles (rather than, in the standard edge coloring problem, having no adjacent pairs of edges). Edge coloring_sentence_108

That is, it is the minimum number of forests into which the edges of the graph may be partitioned into. Edge coloring_sentence_109

Unlike the chromatic index, the arboricity of a graph may be computed in polynomial time. Edge coloring_sentence_110

List edge-coloring is a problem in which one is given a graph in which each edge is associated with a list of colors, and must find a proper edge coloring in which the color of each edge is drawn from that edge's list. Edge coloring_sentence_111

The list chromatic index of a graph G is the smallest number k with the property that, no matter how one chooses lists of colors for the edges, as long as each edge has at least k colors in its list, then a coloring is guaranteed to be possible. Edge coloring_sentence_112

Thus, the list chromatic index is always at least as large as the chromatic index. Edge coloring_sentence_113

The Dinitz conjecture on the completion of partial Latin squares may be rephrased as the statement that the list edge chromatic number of the complete bipartite graph Kn,n equals its edge chromatic number, n. resolved the conjecture by proving, more generally, that in every bipartite graph the chromatic index and list chromatic index are equal. Edge coloring_sentence_114

The equality between the chromatic index and the list chromatic index has been conjectured to hold, even more generally, for arbitrary multigraphs with no self-loops; this conjecture remains open. Edge coloring_sentence_115

Many other commonly studied variations of vertex coloring have also been extended to edge colorings. Edge coloring_sentence_116

For instance, complete edge coloring is the edge-coloring variant of complete coloring, a proper edge coloring in which each pair of colors must be represented by at least one pair of adjacent edges and in which the goal is to maximize the total number of colors. Edge coloring_sentence_117

Strong edge coloring is the edge-coloring variant of strong coloring, an edge coloring in which every two edges with adjacent endpoints must have different colors. Edge coloring_sentence_118

Strong edge coloring has applications in channel allocation schemes for wireless networks. Edge coloring_sentence_119

studied 3-edge-colorings of cubic graphs with the additional property that no two bichromatic cycles share more than a single edge with each other. Edge coloring_sentence_120

He showed that the existence of such a coloring is equivalent to the existence of a drawing of the graph on a three-dimensional integer grid, with edges parallel to the coordinate axes and each axis-parallel line containing at most two vertices. Edge coloring_sentence_121

However, like the standard 3-edge-coloring problem, finding a coloring of this type is NP-complete. Edge coloring_sentence_122

Total coloring is a form of coloring that combines vertex and edge coloring, by requiring both the vertices and edges to be colored. Edge coloring_sentence_123

Any incident pair of a vertex and an edge, or an edge and an edge, must have distinct colors, as must any two adjacent vertices. Edge coloring_sentence_124

It has been conjectured (combining Vizing's theorem and Brooks' theorem) that any graph has a total coloring in which the number of colors is at most the maximum degree plus two, but this remains unproven. Edge coloring_sentence_125

If a 3-regular graph on a surface is 3-edge-colored, its dual graph forms a triangulation of the surface which is also edge colored (although not, in general, properly edge colored) in such a way that every triangle has one edge of each color. Edge coloring_sentence_126

Other colorings and orientations of triangulations, with other local constraints on how the colors are arranged at the vertices or faces of the triangulation, may be used to encode several types of geometric object. Edge coloring_sentence_127

For instance, rectangular subdivisions (partitions of a rectangular subdivision into smaller rectangles, with three rectangles meeting at every vertex) may be described combinatorially by a "regular labeling", a two-coloring of the edges of a triangulation dual to the subdivision, with the constraint that the edges incident to each vertex form four contiguous subsequences, within each of which the colors are the same. Edge coloring_sentence_128

This labeling is dual to a coloring of the rectangular subdivision itself in which the vertical edges have one color and the horizontal edges have the other color. Edge coloring_sentence_129

Similar local constraints on the order in which colored edges may appear around a vertex may also be used to encode straight-line grid embeddings of planar graphs and three-dimensional polyhedra with axis-parallel sides. Edge coloring_sentence_130

For each of these three types of regular labelings, the set of regular labelings of a fixed graph forms a distributive lattice that may be used to quickly list all geometric structures based on the same graph (such as all axis-parallel polyhedra having the same skeleton) or to find structures satisfying additional constraints. Edge coloring_sentence_131

A deterministic finite automaton may be interpreted as a directed graph in which each vertex has the same out-degree d, and in which the edges are d-colored in such a way that every two edges with the same source vertex have distinct colors. Edge coloring_sentence_132

The road coloring problem is the problem of edge-coloring a directed graph with uniform out-degrees, in such a way that the resulting automaton has a synchronizing word. Edge coloring_sentence_133

solved the road coloring problem by proving that such a coloring can be found whenever the given graph is strongly connected and aperiodic. Edge coloring_sentence_134

Ramsey's theorem concerns the problem of k-coloring the edges of a large complete graph Kn in order to avoid creating monochromatic complete subgraphs Ks of some given size s. According to the theorem, there exists a number Rk(s) such that, whenever n ≥ R(s), such a coloring is not possible. Edge coloring_sentence_135

For instance, R2(3) = 6, that is, if the edges of the graph K6 are 2-colored, there will always be a monochromatic triangle. Edge coloring_sentence_136

A path in an edge-colored graph is said to be a rainbow path if no color repeats on it. Edge coloring_sentence_137

A graph is said to be rainbow colored if there is a rainbow path between any two pairs of vertices. Edge coloring_sentence_138

An edge-colouring of a graph G with colours 1. . Edge coloring_sentence_139

. Edge coloring_sentence_140

t is an interval t coloring if all colours are used, and the colours of edges incident to each vertex of G are distinct and form an interval of integers. Edge coloring_sentence_141

Applications Edge coloring_section_13

Edge colorings of complete graphs may be used to schedule a round-robin tournament into as few rounds as possible so that each pair of competitors plays each other in one of the rounds; in this application, the vertices of the graph correspond to the competitors in the tournament, the edges correspond to games, and the edge colors correspond to the rounds in which the games are played. Edge coloring_sentence_142

Similar coloring techniques may also be used to schedule other sports pairings that are not all-play-all; for instance, in the National Football League, the pairs of teams that will play each other in a given year are determined, based on the teams' records from the previous year, and then an edge coloring algorithm is applied to the graph formed by the set of pairings in order to assign games to the weekends on which they are played. Edge coloring_sentence_143

For this application, Vizing's theorem implies that no matter what set of pairings is chosen (as long as no teams play each other twice in the same season), it is always possible to find a schedule that uses at most one more weekend than there are games per team. Edge coloring_sentence_144

Open shop scheduling is a problem of scheduling production processes, in which there are a set of objects to be manufactured, each object has a set of tasks to be performed on it (in any order), and each task must be performed on a specific machine, preventing any other task that requires the same machine from being performed at the same time. Edge coloring_sentence_145

If all tasks have the same length, then this problem may be formalized as one of edge coloring a bipartite multigraph, in which the vertices on one side of the bipartition represent the objects to be manufactured, the vertices on the other side of the bipartition represent the manufacturing machines, the edges represent tasks that must be performed, and the colors represent time steps in which each task may be performed. Edge coloring_sentence_146

Since bipartite edge coloring may be performed in polynomial time, the same is true for this restricted case of open shop scheduling. Edge coloring_sentence_147

study the problem of link scheduling for time division multiple access network communications protocols on sensor networks as a variant of edge coloring. Edge coloring_sentence_148

In this problem, one must choose time slots for the edges of a wireless communications network so that each node of the network can communicate with each neighboring node without interference. Edge coloring_sentence_149

Using a strong edge coloring (and using two time slots for each edge color, one for each direction) would solve the problem but might use more time slots than necessary. Edge coloring_sentence_150

Instead, they seek a coloring of the directed graph formed by doubling each undirected edge of the network, with the property that each directed edge uv has a different color from the edges that go out from v and from the neighbors of v. They propose a heuristic for this problem based on a distributed algorithm for (Δ + 1)-edge-coloring together with a postprocessing phase that reschedules edges that might interfere with each other. Edge coloring_sentence_151

In fiber-optic communication, the path coloring problem is the problem of assigning colors (frequencies of light) to pairs of nodes that wish to communicate with each other, and paths through a fiber-optic communications network for each pair, subject to the restriction that no two paths that share a segment of fiber use the same frequency as each other. Edge coloring_sentence_152

Paths that pass through the same communication switch but not through any segment of fiber are allowed to use the same frequency. Edge coloring_sentence_153

When the communications network is arranged as a star network, with a single central switch connected by separate fibers to each of the nodes, the path coloring problem may be modeled exactly as a problem of edge coloring a graph or multigraph, in which the communicating nodes form the graph vertices, pairs of nodes that wish to communicate form the graph edges, and the frequencies that may be used for each pair form the colors of the edge coloring problem. Edge coloring_sentence_154

For communications networks with a more general tree topology, local path coloring solutions for the star networks defined by each switch in the network may be patched together to form a single global solution. Edge coloring_sentence_155

Open problems Edge coloring_section_14

list 23 open problems concerning edge coloring. Edge coloring_sentence_156

They include: Edge coloring_sentence_157

Edge coloring_unordered_list_0

  • The conjecture of that the chromatic index and fractional index are within one of each other, which would allow the chromatic index to be approximated within one color in polynomial time.Edge coloring_item_0_0
  • Several conjectures of Jakobsen and others on the structure of critical graphs for edge coloring, graphs of class 2 such that any subgraph either has smaller maximum degree or is of class 1. Jakobsen originally conjectured that all critical graphs have an odd number of vertices, but this was eventually disproved. Several other conjectures weakening this one, or bounding the numbers of vertices of critical graphs and critical multigraphs, remain open.Edge coloring_item_0_1
  • Vizing's problem of classifying the maximum degrees that are possible for class 2 planar graphs.Edge coloring_item_0_2
  • The overfull subgraph conjecture of A. J. W. Hilton, stating that graphs with degree at least n/3 are either of class 1 or contain a subgraph with the same degree Δ as the original graph, and with an odd number k of vertices, such that the number of edges in the subgraph is greater than Δ(k − 1)/2, and a similar conjecture by Herbert Grötzsch and Paul Seymour concerning planar graphs in place of high-degree graphs.Edge coloring_item_0_3
  • A conjecture of Amanda Chetwynd and Anthony Hilton (possibly going back earlier to the work of Gabriel Andrew Dirac) that regular graphs with an even number n of vertices and with degree at least n/2 are of class 1.Edge coloring_item_0_4
  • A conjecture of Claude Berge and D. R. Fulkerson that the 6-regular multigraphs formed by doubling every edge of a bridgeless 3-regular simple graph may be edge-colored with six colors.Edge coloring_item_0_5
  • A conjecture of Fiorini and Wilson that every triangle-free planar graph, other than the claw K1,3, is not uniquely 3-edge-colorable.Edge coloring_item_0_6
  • A 2012 conjecture that if G is a d-regular planar multigraph, then G is d-edge-colorable if and only if G is oddly d-edge-connected. This conjecture is a generalization of the four color theorem, which arises at d=3. Maria Chudnovsky, Katherine Edwards, and Paul Seymour proved that an 8-regular planar multigraph has an edge chromatic number of 8.Edge coloring_item_0_7


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Edge coloring.