The Chromatic Number of a Graph

The literature devoted to the applications of computing the chromatic number of a graph is very extensive. Two of the basic applications are the frequency assignment problem and the task scheduling problem. 

We recommend an excellent and comprehensive textbook by Godsil and Royle, [GROl], where more about fractional chromatic number can be found. As for the circular chromatic number of a graph, we refer to nice articles [Vi88, ZhuOl] for rather extensive information. 

This method can be used more generally to find what can be called the "unlabelled chromatic polynomial" of a graph — giving the number of ways of coloring in x colors the vertices of a graph when two colorings are equivalent if one is converted to the other by an automorphism of the graph. 

The subsets Vg are called colour classes. The simplest descriptor that can be defined by a vertex chromatic decomposition is called the chromatic number k((7) [or vertex chromatic number, k((7)] and is the smallest number of colour equivalence classes (i.e. G). In general, there is not a unique chromatic decomposition of a graph with the smallest number of colours. Analogously, the descriptor obtained by an edge chromatic decomposition is called the edge chromatic number k(. ... 

A graph homomorphism G —> is the same as a vertex coloring of G with n colors. In particular, the chromatic number of G, denoted by x(G), is the minimal n such that there exists a graph homomorphism p G Kn see Definition 17.2. 

The first one concerns a collection of transmitters, with certain pairs of transmitters required to have different frequencies (e.g., because they are too close). Clearly, the minimal number of frequencies required for such an assignment is precisely the chromatic number of the graph, whose vertices correspond to the transmitters, with two connected by an edge if and only if they are required to have different frequencies. 

The second problem concerns a collection of tasks that need to be performed. Each task has to be performed exactly once, and the tasks are to be performed in regularly allocated slots (e.g., hours). The only constraint is that certain tasks cannot be performed simultaneously. Again, the minimal number of slots required for the task scheduling is equal to the chromatic number of the graph whose vertices correspond to tasks, with two vertices coimected by an edge if and only if the corresponding tasks cannot be performed simultaneously. 

Graphs whose vertices or edges are symbolically differentiated by assigning a minimal number of different colours to the vertices (or edges) of G such that no two adjacent vertices (or edges) have the same colour (- chromatic decomposition). 

Shortly after it was published, Lov z s resolution of the Kneser conjecture was complemented by finding a maximal subgraph having the same chromatic number as the original Kneser graph. To formulate this result, we recall that a graph G is called vertex-critical if for any vertex v G V G), we have x G) = x G-v) + l. 

---