Question

Design a greedy strategy for finding a proper coloring of a graph using (G) + 1 colors, where (G) denotes the maximum degree of a vertex.

Answer 1

. The elements of S are called colours; the vertices of one colour form a colour class. If |S| = k, we say that c is a k-colouring (often we use S = {1,..., k}). A colouring is proper if adjacent vertices have different colours. A graph is k-colourable if it has a proper k-colouring. The chromatic number χ(G) is the least k such that G is k-colourable. Obviously, χ(G) exists as assigning distinct colours to vertices yields a proper |V(G)|-colouring. An optimal colouring of G is a χ(G)-colouring. A graph G is k-chromatic if χ(G) = k. In a proper colouring, each colour class is a stable set. Hence a k-colouring may also be seen as a partition of the vertex set of G into k disjoint stable sets Si = {v | c(v) = i} for 1 ≤ i ≤ k. Therefore k-colourable are also called k-partite graphs. Moreover, 2-colourable graphs are very often called bipartite. Clearly, if H is a subgraph of G then any proper colouring of G is a proper colouring of H.

the inequality χ(G) ≥ max{χ(C),C connected component of G} because every connected component of G is a subgraph of G. Let us now prove the opposite inequality. LetC1,C2,...,Cp be the connected components of G. For 1 ≤ i ≤ p, let ci be a proper colouring ofCi with colours 1,2,...,χ(Ci). Let c be the union of the ci that is the colouring of G defined by c(v) = ci(v) for all v ∈Ci. Since there is no edge between two vertices in different connected component, c is a proper colouring of G with colours 1,2,...,max{χ(Ci) | 1 ≤ i ≤ p}. Hence χ(G) ≤ max{χ(C),C connected component of G}. Often in the following, we will consider connected graphs.On the algorithmic point of view, one may wonder what is the complexity of computing the chromatic number of graph. Moreover, for evey fixed k, we might ask for the complexity of deciding if a graph is k-colourable. k-COLOURABILITY Input: A graph G. Question: Is G k-colourable? The 1-colourable graphs are the empty graphs (i.e. graphs with no edges). The 2-colourable graphs are the bipartite graphs and can be characterized and recognized in polynomial time (See Section 2.3). Hence for k ≤ 2, k-COLOURABILITY is polynomial-time solvable. In constrast, we now prove that k-COLOURABILITY is N P-complete for all k ≥ 3.