Graph coloring

A coloring of an undirected graph assigns to each node or each edge in the graph to a color.

In graph theory, one usually deals only with so-called " acceptable " or " valid" stains ( see below), and attempts to develop algorithms that find a valid coloring with as few colors for a given graph. Problems of discrete mathematics, but also non- mathematical questions can sometimes be in a coloring problem translating, therefore, the existence or nonexistence of such algorithms is outside the graph theory of interest.

Node colorings

If an undirected graph without multiple edges and a mapping of the set of nodes in the set of natural numbers, it is called a node coloring. The elements of the colors called ( also part of pictures in any countable quantities and not in the natural numbers are considered. However, is not important, necessary is merely the distinctness of the colors). This is called valid or admissible, if ever any two adjacent nodes do not have the same color:

Wherein the set of neighbors of designated.

In this case, k is knotenfärbbar, if there is a valid node of coloring, so that only colors can be used, ie.

An admissible node coloring of a graph is a partition of its vertex set into independent sets ( a subset of the vertex set of a graph is called independent if it contains no two adjacent nodes).

With a full node coloring exists an edge is so with and stained for each pair of colors. That is, for every pair of colors exist neighboring nodes that are colored with these colors.

Number of colorings

If a graph is dyeable, there is a minimum number, so that the graph is knotenfärbbar. This number is called the chromatic number or chromatic number of nodes of the graph and usually labeled. Exists for so many colors, no color are employed symbolically.

Chromatic polynomial of a graph indicates the number of permitted colorings for each number.

Bandwidth

Is a simple graph with nodes and a one-one coloring of the node, called

The bandwidth ( english bandwidth ) of the graph with respect and

The range of the graph. The determination of the bandwidth is one of the few graph theoretical problems, which is also NP-complete for trees.

Properties

• Each K- partiter graph is k - Knotenfärbbar, the partition classes here correspond exactly to the colors. To ensure that all bipartite graphs are 2- colorable.
• Is a graph with edges so true
• The greedy algorithm returns as the upper bound for the chromatic number of a graph of the maximum degree of the graph plus 1 examples that show that this estimate is best possible, are odd cycles and complete graphs. The set of Brooks shows that these are also the only examples.
• For every connected graph that is neither complete nor an odd cycle, its chromatic number is always less than or equal to the maximum degree of the graph.

Node colorings of planar graphs

One of the classic problems of graph theory is the question of how many colors you maximum needed to color a map so that any two adjacent countries have not the same color. This problem can be easily in a node coloring problem on lead (see picture right). The graph theory equivalent question is: What is the Chromatics number of a planar graph? The four-color theorem states that the chromatic number of a planar graph is at most 4. Does the graph of a triangle, it is even 3 - Knotenfärbbar. Nevertheless, determining the chromatic number is NP-hard even for planar graphs.

Algorithms

The determination of the chromatic number of a graph is NP-hard, which means that it is - probably is no algorithm that solves this problem efficiently - from the perspective of complexity theory. The determination of the chromatic number is also one of the problems of Karp's 21 NP- complete problems and one of the first problems for which the NP- completeness was shown. Exceptions are bipartite graphs ( The decision problem whether a given graph is bipartite, has linear time complexity, and, for example, with depth-first search solvable ) and perfect graphs ( exist in perfect graphs polynomial time to compute the chromatic number).

The node coloring problem is NP -complete.

The currently best practical algorithm for determining a node coloring is based on a column generation approach (see literature). Furthermore, there are many coloring heuristics that are looking good colorations according to certain methods and thus provide an upper bound for the chromatic number in case of success.

Applications

Timetable problems can be formulated as graph coloring problems: the nodes of the graph are the events to be placed, and an edge is inserted between two events that can not occur simultaneously. In school, would eg hourly, who are taught by the same teacher and hours in the same class. The possible colors correspond to the assignable time windows.

The red-black tree is balanced by node coloring.

In the same way, for example, register allocation problems processors, bandwidth allocation problems and many problems of mathematics can be formulated as a graph coloring problems.

Generalizations

A generalization of the node coloring is the notion of list coloring. Here, each node is assigned a "list" of available colors and the graph will now get a valid coloring from these lists. Furthermore, there is the total dyeing both nodes and edges will be colored at the.