Graph Coloring

Graph Colouring: Coloring the vertices of a graph such that no two adjacent vertices have the same colour.


Chromatic Number(X(G)): The Min no of colour required to colour thegiven graph G.


Graph(G) Chromatic Number X(G)
Null(Nn) 1
Cycle Cn

2     if n is even

3    if n is odd

Wheel Wn

3   if n is even

4   if n is odd

Kn n
km,n 2



1. G is a graph with n vertices then X(G) <= n

2. Kn is a sub graph of Graph G X(G) >= n

3. X(G) <=1+Δ , where Δ is max degree in the graph.

4. X(G) >= |v|/|v|-δ , 

where δ is min degree in the graph.


The following statement are equivalent 

1) G is bipaptite 

2) G is 2-colourable

3) Every cycle in G is even cycle.



Example 1:

 what is its chromatic number?




first arrange in decending order of degree V1 ,V6,V2,V3,V4,V5

we will assign color c1 to  V1 ,V6 now coming to V2 it should be diff from V1 and V6 so we gave c2 to V2 and V3 now same will be follow for V4 and V5 we gave it c3.

therefore we need 3 color.