Edge coloring - AbsoluteAstronomy.com

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, an edge coloring of a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

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

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

. 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 graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

s and high-degree planar graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s, the number of colors is always , and for multigraph

Multigraph

In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....

s, 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

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of 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

Cycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...

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

Complete graph

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

with vertices may have its edges colored with colors when is an even number; this is a special case of Baranyai's theorem

Baranyai's theorem

In combinatorial mathematics, Baranyai's theorem deals with the decompositions of complete hypergraphs.-Statement of the theorem:The statement of the result is that if 2\le r...

. 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 graph

Odd graph

In the mathematical field of graph theory, the odd graphs On are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.-Definition and examples:...

s, -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

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

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

Definitions

As with its vertex counterpart

Graph coloring

, 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 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

Line graph

In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...

, 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 (proper) -edge-coloring. A graph that can be assigned a (proper) -edge-coloring is said to be -edge-colorable. The smallest number of colors needed in a (proper) 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

Graph coloring

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 multigraph

Multigraph

s in which two or more edges may 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

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

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 (such as the odd complete graphs); for such graphs, by the handshaking lemma

Handshaking lemma

In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree...

, 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

Petersen graph

is regular, with and with edges in its perfect matchings, but it does not have a 3-edge-coloring.

Vizing's theorem

The edge chromatic number of a graph is very closely related to the maximum degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum 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 (named for Vadim G. Vizing

Vadim G. Vizing

Vadim Georgievich Vizing is a Ukrainian mathematician known for his contributions to graph theory, and especially for Vizing's theorem stating that the edges of any graph with maximum degree Δ can be colored with at most Δ + 1 colors.- Biography :Vizing was born in Kiev on March...

who published it in 1964) 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.

For instance, when , the graph must itself be a matching, with no two edges adjacent, and its edge chromatic number is one. That is, all graphs with are of class 1. When , the graph must be a disjoint union

Disjoint union

In mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a disjoint union...

of paths

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

and cycles

Cycle (graph theory)

In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...

; in this case, it can be 2-edge-colored if and only if all of the cycles have even length. That is, a graph with is of class 1 if and only if it is bipartite

Bipartite graph

. More generally, according to a theorem of , every bipartite graph is of class 1, regardless of its maximum degree. However, for non-bipartite graphs with larger maximum degree than two, it is much more difficult to distinguish class 1 graphs from class 2 graphs: proved that it is NP-complete

NP-complete

to determine whether a graph is of class 1.

Several authors have provided additional conditions that classify some graphs as being of class 1 or class 2, but do not provide a complete classification. For instance, if the vertices of the maximum degree in a graph form an independent set

Independent set

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...

, or more generally if the induced subgraph for this set of vertices is a forest, then must be of class 1.

showed that almost all

Almost all

In mathematics, the phrase "almost all" has a number of specialised uses."Almost all" is sometimes used synonymously with "all but finitely many" or "all but a countable set" ; see almost....

graphs are of class 1. That is, in the Erdős–Rényi model

Erdos–Rényi model

In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...

of random graphs, in which all -vertex graphs are equally likely, let be the probability that an -vertex graph drawn from this distribution is of class 1; then approaches one in the limit as goes to infinity. For more precise bounds on the rate at which converges to one, see .

Regular graphs

A 1-factorization of a k-regular graph

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

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

(3-regular) graph is sometimes called a Tait coloring.

Not every regular graph has a 1-factorization; for instance, the Petersen graph

Petersen graph

does not. More generally the snark

Snark (graph theory)

In the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by only three colors without two edges of the same color meeting at a...

s 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

Ernst Steinitz

Ernst Steinitz was a German mathematician.- Biography :Steinitz was born in Laurahütte , Silesia, Germany , the son of Sigismund Steinitz, a Jewish coal merchant, and his wife Auguste Cohen; he had two brothers. He studied at the University of Breslau and the University of Berlin, receiving his Ph.D...

in his PhD thesis.

Planar graphs

showed that a planar graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

is of class 1 if its maximum degree is at least eight.
In contrast, he observed that for any maximum degree in the range from two to five, there exist
planar graphs of class 2. For degree two, any odd cycle is such a graph, and for degree three, four, and five, these graphs can be constructed from platonic solid

Platonic solid

In geometry, a Platonic solid is a convex polyhedron that is regular, in the sense of a regular polygon. Specifically, the faces of a Platonic solid are congruent regular polygons, with the same number of faces meeting at each vertex; thus, all its edges are congruent, as are its vertices and...

s by replacing a single edge by a path of two adjacent edges.

In Vizing's planar graph conjecture, states that all simple, planar graphs with maximum degree six or seven are of class 1, closing the remaining possible cases.
partially proved Vizing's planar graph conjecture by showing that all planar graphs with maximum degree seven are of class 1.
Thus, the only case of the conjecture that remains unsolved is that of maximum degree six. This conjecture has implications for the total coloring conjecture

Total coloring

In graph theory, total coloring is a type of coloring on the vertices and edges of a graph.When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...

.

The planar graphs of class 2 constructed by subdivision of the platonic solids are not regular: they have vertices of degree two as well as vertices of higher degree.
The four color theorem

Four color theorem

In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...

, on vertex coloring of planar graphs, is equivalent to the statement that every bridgeless 3-regular planar graph is of class one . This statement is now known to be true, due to the proof of the four color theorem by .

Graphs on nonplanar surfaces

In 1969, Branko Grünbaum

Branko Grünbaum

Branko Grünbaum is a Croatian-born mathematician and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel....

conjectured that every 3-regular graph with a polyhedral embedding on any two-dimensional oriented manifold such as a torus

Torus

In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...

must be of class one. In this context, a polyhedral embedding is a graph embedding

Graph embedding

In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...

such that every face of the embedding is topologically a disk and such that the dual graph

Dual graph

In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...

of the embedding is simple, with no self-loops or multiple adjacencies. If true, this would be a generalization of the four color theorem, which was shown by Tait to be equivalent to the statement that 3-regular graphs with a polyhedral embedding on a sphere

Sphere

A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...

are of class one. However, showed the conjecture to be false by finding snarks

Snark (graph theory)

that have polyhedral embeddings on high-genus orientable surfaces. Based on this construction, he also showed that it is NP-complete to tell whether a polyhedrally embedded graph is of class 1.

Multigraphs

For multigraph

Multigraph

s, 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

Shannon multigraph

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by , are a special type of triangle graphs, which are used in the field of edge coloring in particular....

, a multigraph with three vertices and three bundles of parallel edges connecting each of the three pairs of vertices. In this example, (each vertex is incident to only two out of the three bundles of parallel edges) but the edge chromatic number is (there are edges in total, and every two edges are adjacent, so all edges must be assigned different colors to each other). 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 (for which ).

Algorithms

Because the problem of testing whether a graph is class 1 is NP-complete

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 graph

Bipartite graph

s 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

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

. The total time for his algorithm is .

For planar graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s 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 .

Algorithms that use more than the optimal number of colors

describe a polynomial time algorithm for coloring any graph with colors, where is the maximum degree of the graph. That is, the algorithm uses the optimal number of colors for graphs of class 2, and uses at most one more color than necessary for all graphs. Their algorithm follows the same strategy as Vizing's original proof of his theorem: it starts with an uncolored graph, and then repeatedly finds a way of recoloring the graph in order to increase the number of colored edges by one. More specifically, suppose that is an uncolored edge in a partially colored graph. The algorithm of Misra and Gries may be interpreted as constructing a directed pseudoforest

Pseudoforest

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be...

(a graph in which each vertex has at most one outgoing edge) on the neighbors of : for each neighbor of , the algorithm finds a color that is not used by any of the edges incident to , finds the vertex (if it exists) for which edge has color , and adds as an edge to . If the pseudoforest constructed in this way contains a path from to a vertex that has no outgoing edges in , then there is a color that is available both at and . Recoloring edge with color allows the remaining edge colors to be shifted one step along this path: for each vertex in the path, edge takes the color that was previously used by the successor of in the path. This leads to a new coloring that includes edge . If, on the other hand, the path starting from in the pseudoforest leads to a cycle, let be the neighbor of at which the path joins the cycle, let be the color of edge , and let be a color that is not used by any of the edges at vertex . Then swapping colors and on a Kempe chain

Kempe chain

In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem.-History:Kempe chains were first used by Alfred Kempe in his attempted proof of the four colour theorem. Even though his proof turned out to be incorrect, the method of Kempe chains is crucial to the...

either breaks the cycle or the edge on which the path joins the cycle, leading to the previous case. With some simple data structures to keep track of the colors that are used and available at each vertex, the construction of and the recoloring steps of the algorithm can all be implemented in time , where is the number of vertices in the input graph. Since these steps need to be repeated times, with each repetition increasing the number of colored edges by one, the total time is . In an unpublished technical report, claimed a faster

time bound for the same problem of coloring with colors.

For multigraphs, present the following algorithm, which they attribute to Eli Upfal

Eli Upfal

Eli Upfal is a computer science researcher currently a professor in the computer science department at Brown University. He completed his undergraduate studies in mathematics and statistics at the Hebrew University, Israel in 1978, received an M.Sc...

. Make the input multigraph Eulerian by adding a new vertex connected by an edge to every odd-degree vertex, find an Euler tour, and choose an orientation for the tour. Form a bipartite graph in which there are two copies of each vertex of , one on each side of the bipartition, with an edge from a vertex on the left side of the bipartition to a vertex on the right side of the bipartition whenever the oriented tour has an edge from to in . Apply a bipartite graph edge coloring algorithm to . Each color class in corresponds to a set of edges in that form a subgraph with maximum degree two; that is, a disjoint union of paths and cycles, so for each color class in it is possible to form three color classes in . The time for the algorithm is bounded by the time to edge color a bipartite graph, using the algorithm of . The number of colors this algorithm uses is at most

, close to but not quite the same as Shannon's bound of

. It may also be made into a parallel algorithm

Parallel algorithm

In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...

in a straightforward way. In the same paper, Karloff and Shmoys also present a linear time algorithm for coloring multigraphs of maximum degree three with four colors (matching both Shannon's and Vizing's bounds) that operates on similar principles: their algorithm adds a new vertex to make the graph Eulerian, finds an Euler tour, and then chooses alternating sets of edges on the tour to split the graph into two subgraphs of maximum degree two. The paths and even cycles of each subgraph may be colored with two colors per subgraph. After this step, each remaining odd cycle contains at least one edge that may be colored with one of the two colors belonging to the opposite subgraph. Removing this edge from the odd cycle leaves a path, which may be colored using the two colors for its subgraph.

A greedy coloring

Greedy coloring

In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color...

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 colors, which may be nearly twice as many number of colors as is necessary. However, it has the advantage that it may be used in the online algorithm

Online algorithm

In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from...

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

Several authors have made conjectures that imply that the fractional chromatic index

Fractional coloring

Fractional coloring is a topic in a young branch of graph theory known as fractional graph theory. It is a generalization of ordinary graph coloring. In a traditional graph coloring, each vertex in a graph is assigned some color, and adjacent vertices — those connected by edges — must be assigned...

of any multigraph (a number that can be computed in polynomial time using linear programming

Linear programming

Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...

) is within one of the chromatic index. If these conjectures are true, it would be possible to compute a number that is never more than one off from the chromatic index in the multigraph case, matching what is known via Vizing's theorem for simple graphs. Although unproven in general, these conjectures are known to hold when the chromatic index is at least

, as can happen for multigraphs with sufficiently large multiplicity.

Exact algorithms

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.
As showed, it is possible to test whether a graph has a 3-edge-coloring in time , while using only polynomial space. Although this time bound is exponential, it is significantly faster than a brute force search over all possible assignments of colors to edges. Every biconnected

Biconnected graph

In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.In other words, a biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected.The property of being 2-connected...

3-regular graph with vertices has 3-edge-colorings; all of which can be listed in time (somewhat slower than the time to find a single coloring); as Greg Kuperberg

Greg Kuperberg

Greg Kuperberg is an American mathematician of Polish birth known for his contributions to geometric topology, quantum algebra, and combinatorics. Kuperberg is a professor of mathematics at the University of California, Davis....

observed, the graph of a prism

Prism (geometry)

In geometry, a prism is a polyhedron with an n-sided polygonal base, a translated copy , and n other faces joining corresponding sides of the two bases. All cross-sections parallel to the base faces are the same. Prisms are named for their base, so a prism with a pentagonal base is called a...

over an -sided polygon has many colorings, showing that this bound is tight.

By applying exact algorithms for vertex coloring to the line graph

Line graph

In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...

of the input graph, it is possible to optimally edge-color any graph with edges, regardless of the number of colors needed, in time and exponential space, or in time and only polynomial space .

Because edge coloring is NP-complete even for three colors, it is unlikely to be fixed parameter tractable

Parameterized complexity

Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...

when parametrized by the number of colors. However, it is tractable for other parameters. In particular, showed that for graphs of treewidth , an optimal edge coloring can be computed in time , a bound that depends superexponentially on but only linearly on the number of vertices in the graph.

formulate the edge coloring problem as an integer program and describe their experience using an integer programming solver to edge color graphs. However, they did not perform any complexity analysis of their algorithm.

Additional properties

A graph is uniquely

Uniquely colorable graph

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible k-coloring up to permutation of the colors.-Examples:...

-edge-colorable if there is only one way of partitioning the edges into color classes, ignoring the possible permutations of the colors. For , the only uniquely -edge-colorable graphs are paths, cycles, and star

Star (graph theory)

In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...

s, but for other graphs may also be uniquely -edge-colorable. 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 graph

Generalized Petersen graph

In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized...

s for . The only known nonplanar uniquely 3-colorable graph is the generalized Petersen graph , and it has been conjectured that no others exist.
investigated the non-increasing sequences of numbers with the property that there exists a proper edge coloring of a given graph with edges of the first color, edges of the first color, etc. They observed that, if a sequence is feasible in this sense, and is greater in lexicographic order than a sequence with the same sum, then is also feasible. For, if in lexicographic order, then can be transformed into by a sequence of steps, each of which reduces one of the numbers by one unit and increases another later number
with by one unit. In terms of edge colorings, starting from a coloring that realizes , each of these same steps may be performed by swapping colors and on a Kempe chain

Kempe chain

, a maximal path of edges that alternate between the two colors. In particular, any graph has an equitable

Equitable coloring

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that*No two adjacent vertices have the same color, and...

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.

The De Bruijn–Erdős theorem may be used to transfer many edge coloring properties of finite graphs to infinite graphs. For instance, Shannon's and Vizing's theorems relating the degree of a graph to its chromatic index both generalize straightforwardly to infinite graphs.

considers the problem of finding a graph drawing

Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...

of a given cubic graph

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. 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. For instance, the drawing of the utility graph as the edges and long diagonals of a regular hexagon represents a 3-edge-coloring of the graph in this way. 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

K-edge-connected graph

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G = be an arbitrary graph....

. 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

Bipartite double cover

In graph theoretic mathematics, the bipartite double cover of an undirected graph G is a bipartite covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs G × K2...

of the graph is 3-edge-connected, and if deleting any monochromatic pair of edges leads to a subgraph that is still non-bipartite. 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

Existential theory of the reals

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form...

, a complexity class at least as difficult as being NP-complete.

As well as being related to the maximum degree and maximum matching number of a graph, the chromatic index is closely related to the linear arboricity

Arboricity

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...

of a graph , the minimum number of linear forests (disjoint unions of paths) into which the graph's edges may be partitioned. A matching is a special kind of linear forest, and in the other direction, any linear forest can be 2-edge-colored, so for every it follows that . Akiyama's conjecture states that

, from which it would follow more strongly that . For graphs of maximum degree three, is always exactly two, so in this case the bound matches the bound given by Vizing's theorem.

Other types of edge coloring

The Thue number

Thue number

In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. and named by them after mathematician Axel Thue, who studied the squarefree words used to define this number.Alon et al...

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.

The arboricity

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). That is, it is the minimum number of forests into which the edges of the graph may be partitioned into. Unlike the chromatic index, the arboricity of a graph may be computed in polynomial time.

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. The list chromatic index of a graph is the smallest number with the property that, no matter how one chooses lists of colors for the edges, as long as each edge has at least colors in its list, then a coloring is guaranteed to be possible. Thus, the list chromatic index is always at least as large as the chromatic index. The Dinitz conjecture

Dinitz conjecture

In combinatorics, the Dinitz conjecture is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin....

on the completion of partial Latin square

Latin square

In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...

s may be rephrased as the statement that the list edge chromatic number of the complete bipartite graph

Complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...

equals its edge chromatic number, . resolved the conjecture by proving, more generally, that in every bipartite graph the chromatic index and list chromatic index are equal. 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.

Many other commonly studied variations of vertex coloring have also been extended to edge colorings. For instance, complete edge coloring is the edge-coloring variant of complete coloring

Complete coloring

In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper...

, 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. Strong edge coloring is the edge-coloring variant of strong coloring

Strong coloring

In graph theory, a strong coloring, with respect to a partition of the vertices into subsets of equal sizes, is a vertex coloring in which every color appears exactly once in every partition....

, an edge coloring in which every two edges with adjacent endpoints must have different colors. Strong edge coloring has applications in channel allocation schemes

Channel allocation schemes

In radio resource management for wireless and cellular network, channel allocation schemes are required to allocate bandwidth and communication channels to base stations, access points and terminal equipment...

for wireless networks. Acyclic edge coloring is the edge-coloring variant of acyclic coloring

Acyclic coloring

In graph theory, an acyclic coloring is a vertex coloring in which every 2-chromatic subgraph is acyclic.The acyclic chromatic number A of a graph G is the least number of colors needed in any acyclic coloring of G....

, an edge coloring for which every two color classes form an acyclic subgraph (that is, a forest).

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. He showed that the existence of such a coloring is equivalent to the existence of a drawing of the graph

Graph drawing

on a three-dimensional integer grid, with edges parallel to the coordinate axes and each axis-parallel line containing at most two vertices. However, like the standard 3-edge-coloring problem, finding a coloring of this type is NP-complete.

Total coloring

Total coloring

is a form of coloring that combines vertex and edge coloring, by requiring both the vertices and edges to be colored. 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. 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.

If a 3-regular graph on a surface is 3-edge-colored, its dual graph

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. 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. 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. 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. 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. For each of these three types of regular labelings, the set of regular labelings of a fixed graph forms a distributive lattice

Distributive lattice

In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...

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.

A deterministic finite automaton may be interpreted as a directed graph

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

in which each vertex has the same out-degree , and in which the edges are -colored in such a way that every two edges with the same source vertex have distinct colors. 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

Synchronizing word

In computer science, more precisely, in the theory of deterministic finite automata , a synchronizing word or reset sequence is a word in the input alphabet of the DFA which sends any state of the DFA to one and the same state...

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

Ramsey's theorem

Ramsey's theorem

In combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...

concerns the problem of -coloring the edges of a large complete graph

Complete graph

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

in order to avoid creating monochromatic complete subgraphs of some given size . According to the theorem, there exists a number such that, whenever , such a coloring is not possible. For instance, , that is, if the edges of the graph are 2-colored, there will always be a monochromatic triangle.

Applications

Edge colorings of complete graphs may be used to schedule a round-robin tournament

Round-robin tournament

A round-robin tournament is a competition "in which each contestant meets all other contestants in turn".-Terminology:...

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

National Football League

The National Football League is the highest level of professional American football in the United States, and is considered the top professional American football league in the world. It was formed by eleven teams in 1920 as the American Professional Football Association, with the league changing...

, 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. 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.

Open shop scheduling

Open Shop Scheduling

The open shop scheduling problem is a scheduling problem where, given n jobs and m workstations, each job has to visit a workstation at least once. The order in which this happens is not relevant .- NP-hardness :The OSSP can be solved in polynomial time for two machines...

is a problem of scheduling production processes

Scheduling (production processes)

Scheduling is an important tool for manufacturing and engineering, where it can have a major impact on the productivity of a process. In manufacturing, the purpose of scheduling is to minimize the production time and costs, by telling a production facility when to make, with which staff, and on...

, 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. 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. Since bipartite edge coloring may be performed in polynomial time, the same is true for this restricted case of open shop scheduling.

study the problem of link scheduling for time division multiple access

Time division multiple access

Time division multiple access is a channel access method for shared medium networks. It allows several users to share the same frequency channel by dividing the signal into different time slots. The users transmit in rapid succession, one after the other, each using its own time slot. This...

network communications protocols on sensor networks as a variant of edge coloring. 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. 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. 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 has a different color from the edges that go out from and from the neighbors of . They propose a heuristic for this problem based on a distributed algorithm for -edge-coloring together with a postprocessing phase that reschedules edges that might interfere with each other.

In fiber-optic communication

Fiber-optic communication

Fiber-optic communication is a method of transmitting information from one place to another by sending pulses of light through an optical fiber. The light forms an electromagnetic carrier wave that is modulated to carry information...

, the path coloring

Path coloring

In graph theory, path coloring usually refers to one of two problems:* The problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors. Set R and graph G are provided at input. This formulation is equivalent to vertex...

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. Paths that pass through the same communication switch but not through any segment of fiber are allowed to use the same frequency. When the communications network is arranged as a star network

Star network

Star networks are one of the most common computer network topologies. In its simplest form, a star network consists of one central switch, hub or computer, which acts as a conduit to transmit messages...

, 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. 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.

Open problems

list 23 open problems concerning edge coloring. They include:

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.
Several conjectures of Jakobsen and others on the structure of critical graph
Critical graph
In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph....

s 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.
Vizing's problem of classifying the maximum degrees that are possible for class 2 planar graphs.
The overfull subgraph conjecture of A. J. W. Hilton, stating that graphs with degree at least are either of class 1 or contain a subgraph with the same degree as the original graph, and with an odd number of vertices, such that the number of edges in the subgraph is greater than , and a similar conjecture by Herbert Grötzsch
Herbert Grötzsch
Camillo Herbert Grötzsch was a mathematician from Halle, Germany. Grötzsch worked in graph theory. He was the discoverer and eponym of the Grötzsch graph, a triangle-free graph that requires four colors in any graph coloring, and Grötzsch's theorem, the result that every triangle-free planar graph...

and Paul Seymour concerning planar graphs in place of high-degree graphs.
A conjecture of Chetwynd and Hilton (possibly going back earlier to the work of Gabriel Andrew Dirac
Gabriel Andrew Dirac
Gabriel Andrew Dirac was a mathematician who mainly worked in graph theory. He stated a sufficient condition for a graph to contain a Hamiltonian circuit.Dirac received his Ph.D...

that regular graphs with an even number of vertices and with degree at least are of class 1.
A conjecture of Claude Berge
Claude Berge
Claude Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. He is particularly remembered for his famous conjectures on perfect graphs and for Berge's lemma, which states that a matching M in a graph G is maximum if and only if there is in...

and D. R. Fulkerson
D. R. Fulkerson
Delbert Ray Fulkerson was a mathematician who co-developed the Ford-Fulkerson algorithm, one of the most well-known algorithms to solve the maximum flow problem in networks....

that the 6-regular multigraphs formed by doubling every edge of a bridgeless 3

External links

Proof of Vizing's theorem at PlanetMath
PlanetMath
PlanetMath is a free, collaborative, online mathematics encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be comprehensive, the project is hosted by the Digital...

.

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.