Edge Coloring - Additional Properties

Additional Properties

A graph is uniquely k-edge-colorable if there is only one way of partitioning the edges into k color classes, ignoring the k! possible permutations of the colors. 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. 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. 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.

Folkman & Fulkerson (1969) 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 first color, etc. 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. 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. 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. 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.

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.

Richter (2011) 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. 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 K3,3 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. 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. 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.

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 la(G) of a graph G, 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 G it follows that la(G) ≤ χ′(G) ≤ 2 la(G). Akiyama's conjecture states that, from which it would follow more strongly that 2 la(G) − 2 ≤ χ′(G) ≤ 2 la(G). For graphs of maximum degree three, la(G) is always exactly two, so in this case the bound χ′(G) ≤ 2 la(G) matches the bound given by Vizing's theorem.

Read more about this topic:  Edge Coloring

Famous quotes containing the words additional and/or properties:

    The mere existence of an additional child or children in the family could signify Less. Less time alone with parents. Less attention for hurts and disappointments. Less approval for accomplishments. . . . No wonder children struggle so fiercely to be first or best. No wonder they mobilize all their energy to have more or most. Or better still, all.
    Adele Faber (20th century)

    The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.
    John Locke (1632–1704)