Chromatic number

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(. ... 

The chromatic information index (or vertex chromatic information index) [Mow-showitz, 1968d] is the minimum value of the mean information content of all possible vertex chromatic decompositions with a number of colours equal to the vertex chromatic number and is defined as ... 

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 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. 

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. 

Much of the same can be said about running tests to jueld lower bounds for the chromatic number. Even the most immediate one, computing the clique number, is not good, since this is an NP-complete problem as well. The existence of cliques of a fixed size can be decided in poljmomial time, but does not provide a very interesting test. 

Proof. Let G be the graph under consideration. Since having multiple edges does not change the chromatic number, we can assume that G is a simple graph. 

Kneser Graphs as State Graphs and Fractional Chromatic Number... 

Definition 17.18. LetG be a graph. The circular chromatic number ofG... 

Considering the elementary definition of the Kneser graphs, it turned out to be surprisingly difHcult to determine their chromatic numbers. 

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. 

Theorem 17.21 was generalized in 1986 to the case of hypergraphs. To start with, recall the standard way to extend the notion of the chromatic number to hypergraphs. 

Definition 17.32. For a hypergraph H, the chromatic number xi H) is, by definition, the minimal number of colors needed to color the vertices ofTL so that no hyperedge is monochromatic. 

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. 

---