Graph Coloring Problem

The graph coloring problem consists in an assignment of integer labels {1,2,3,…} (called colors) to vertices of an undirected graph so that:

- no two adjacent vertices get the same color (correct coloring);

- a minimum possible number of colors is applied.

Definition 8.6. The minimum possible number of different colors required for correct coloring of vertices of a graph G = <V_G, E_G > is called the chromatic number of G and is denoted by c(G).

If |E_G| ¹ 0 or G is not a complete graph then c(G) Î { 2, …, |V_G| - 1}.

Some important practical problems are presented as a graph coloring problem. Here is an example of a scheduling problem. Let {t₁, t₂, …, t_n} denote a set of technological operations to be performed in shortest time. In a graph, operations (now vertices) t_i and t_j are connected by an edge if they cannot be performed at the same time. By doing so we convert the problem of operation scheduling into the problem of minimum correct coloring of graph vertices. One color corresponds to the same start moment of the operations-vertices labelled by this color.

Suppose, there are 6 operations connected into such a graph.

Using some graph coloring algorithm, we partition the set of vertices into such subsets: {B} with color 1, {C, F} with color 2 and {A, D, G} with color 3. Taking into account the specified sequences of operations (B and F after A, and F after B), the operations are scheduled for execution in parallel so:

- {A, D, G} are performed in the first turn.

- {B}is done in the second turn.

- {C, F} are carried out in the third turn.

Note: Directions of edges are ignored at the stage of vertex coloring. These directions are used to choose an appropriate time slot (a turn in the schedule) for each set of operations.

The above example shows the necessity for an efficient graph coloring algorithm.