Edge Coloring - Other Types of Edge Coloring

Other Types of Edge Coloring

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.

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). 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 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. Thus, the list chromatic index is always at least as large as the chromatic index. 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. Galvin (1995) 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, 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, an edge coloring in which every two edges with adjacent endpoints must have different colors. Strong edge coloring has applications in channel allocation schemes for wireless networks. Acyclic edge coloring is the edge-coloring variant of acyclic coloring, an edge coloring for which every two color classes form an acyclic subgraph (that is, a forest).

Eppstein (2008) 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 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 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 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 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 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. 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. Trahtman (2009) 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 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 nR(s), such a coloring is not possible. For instance, R2(3) = 6, that is, if the edges of the graph K6 are 2-colored, there will always be a monochromatic triangle.

Read more about this topic:  Edge Coloring

Famous quotes containing the words types and/or edge:

    Our major universities are now stuck with an army of pedestrian, toadying careerists, Fifties types who wave around Sixties banners to conceal their record of ruthless, beaverlike tunneling to the top.
    Camille Paglia (b. 1947)

    The tongues of mocking wenches are as keen
    As is the razor’s edge invisible.
    William Shakespeare (1564–1616)