SKEDSOFT

Introduction: The chromatic number, (G), of a graph G is the minimum number of independent subsets that partition the vertex set of G. Any such minimum partition is called a chromatic partition of V (G).

A vertex coloring of G is a map f : V (G) → C, where C is a set of distinct colors; it is proper if adjacent vertices of G receive distinct colors of C; that is, if uv ∈ E(G) then f(u) 6= f(v). Thus (G) is the minimum cardinality of C for which there exists a proper vertex coloring of G by colors of C. Clearly, in any proper vertex coloring of G, the vertices that receive the same color are independent. The vertices that receive a particular color make up a color class. Thus, in any chromatic partition of V (G), the parts of the partition constitute the color classes. This allows an equivalent way of defining the chromatic number.

Definition . The chromatic number of a graph G is the minimum number of colors needed for a proper vertex coloring of G. If (G) = k, G is said to be k-chromatic.
For example, the chromatic number of the graph in Figure 3.1 is 3.

Definition . A k-coloring of a graph G is a vertex coloring of G that uses k colors.

Definition. A graph G is said to be k-colorable, if G admits a proper vertex coloring using k colors.

Thus, (G) = k if graph G is k-colorable but not (k − 1)-colorable. In considering the chromatic number of a graph only the adjacency of vertices is taken into account. A graph with a self-loop is regarded as uncolorable, since the endpoint of the self-loop is adjacent to itself. Moreover, a multiple adjacency has no more effect on the colors of its endpoints than a single adjacency. As a consequence, we may restrict ourselves to simple graphs when dealing with chromatic numbers.
It is clear that (G) = 1 if and only if G has no edges and (G) = 2 if and only if G is bipartite.