Edge coloring

In graph theory, an edge coloring is a mapping that maps each edge of the graph, a ( abstract ) color. The term is closely related to node coloring.

Definition

For an undirected multigraph is called a mapping of the set of edges in the set of natural numbers an edge coloring of. The elements of are called in this context colors. This is called valid or permitted if any of two adjacent edges and applies that. Has an edge coloring, so that at most k colors in the image area of occur is called k- edge- G.

The smallest k for which is k- edge-colourable, called chromatic index, edge coloring number or Kantenchromatische number of the graph and is usually denoted by.

Properties

By the theorem of Vizing the chromatic index of a simple graph is at least as large as its maximum extent, but at most one greater than this, ie formally:

Graph called Class 1 graphs, graphs with called class 2 graphs (since the estimation of the sentence shall not apply to multi- graph, multigraph class 2 graphs are called when applies ). To decide whether a graph class 1 or class 2 (classification problem), is NP -complete. That is, although the maximum degree is easy to determine and the chromatic index can take only one of two possible values ​​, the problem is, for a given graph to accurately determine this value a NP-hard.

For bipartite graphs. To ensure that all bipartite graph class are 1 - graphs.

Duality for vertex coloring

The determination of an edge coloring is to determine a vertex coloring dual in such a way that an edge coloring of a graph is exactly one node coloring of the edges of the graph. It follows that the following applies. The kantenchromatische number of a graph is precisely the chromatic number of line graphs. Despite this close relationship, the problems are difficult to solve and the different available estimates differ significantly.

Generalizations

A significant generalization of the edge coloring is the notion of list coloring. Here is a list of available colors is specified for each edge ( or node ) and the graph will now get a valid edge coloring from these lists. Furthermore, there is the total dyeing both nodes and edges will be colored at the.