Edge coloring

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.

[1] 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.

Soifer (2008) 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.

As Biggs (1972) 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.

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.

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.

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

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

In a result that inspired Vizing,[10] Shannon (1949) 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).

In the case of bipartite graphs or multigraphs with maximum degree Δ, the optimal number of colors is exactly Δ. Cole, Ost & Schirra (2001) 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 Cole & Hopcroft (1982) and Alon (2003).

The algorithm of Alon (2003) 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.

Finally, Alon applies an observation of Gabow (1976), 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.

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

For d-regular graphs which are pseudo-random in the sense that their adjacency matrix has second largest eigenvalue (in absolute value) at most d1−ε, d is the optimal number of colors (Ferber & Jain 2020).

For multigraphs, Karloff & Shmoys (1987) present the following algorithm, which they attribute to Eli Upfal.

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.

[11] 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.

[13] 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 this time bound is exponential, it is significantly faster than a brute force search over all possible assignments of colors to edges.

Every biconnected 3-regular graph with n vertices has O(2n/2) 3-edge-colorings; all of which can be listed in time O(2n/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 Ω(2n/2) colorings (lower instead of upper bound), showing that this bound is tight.

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.

[22] Strong edge coloring has applications in channel allocation schemes for wireless networks.

[28] Eppstein (2013) 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.

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

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.

[30] 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.

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

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.