Higher Engineering Mathematics

Professor P N Agrawal
Department of Mathematics
Indian Institute of Technology Roorkee
Lecture 37
Coloring of Graphs - I

(Refer Slide Time: 1:05)

Hello friends, welcome to my lecture on Coloring of Graphs. Let us consider a graph G

vertex coloring are simply a coloring of G is an assignment to the vertices of G such that
adjacent vertices have different colors. We say that G is N colorable if there exist coloring of
G which uses N colors. The minimum number of colors needed to paint a graph G is called
the chromatic number of the graph G and is denoted by χ (G). Now we shall discuss an
algorithm by Welch and Powell for coloring of graph G. We will decide that this algorithm
does not always yield minimal coloring of G.
(Refer Slide Time: 1:18)

Now, let us see what is the Welch Powell algorithm? The input is the graph G, the 1 st step is
order the vertices of G according to the decreasing degrees okay so we will find the decrease
of all the vertices of the graph and then arrange them in the order of decreasing degrees.
Now, step 2 is assign one color C 1 to the 1st vertex okay and then 1st vertex means the vertex
with the highest degree, and then in sequential order assign C 1 color to each vertex which is
not adjacent to the previous vertex that is vertex with the highest degree and which was
assigned C 1 okay. Repeat step 2 with 2nd color C 2 and the subsequence of non-colored
vertices, so in the step 3 we shall start repeating the step 2 with 2 nd color. Now in the step 4
we repeat step 3 with the 3rd color C 3 and 4th color C 4 and so on until all vertices are colored
and then we exit.
(Refer Slide Time: 2:28)

So, let us see how we do this, let us consider this graph okay this graph let us consider. In this
graph you see there are 8 vertices okay, we have to find degrees of each vertex and then
arrange them in the order of decreasing degrees. So degree of A 1, let us 1st find the degree of
A 1, degree of A 1 is 1, 2, 3, 4, degree of A 2 is 1, 2, 3, 4, degree of A 3 is 1, 2, 3, 4, 5, degree of
A 4 is 1, 2, 3, 4, Degree of is 5, A 5 has degree you see 1, 2, 3, 4, 5, 6 and then degree of A 6 so
your 1, 2, 3, degree of A 7 okay degree of A 7 is 1, 2, 3, 4, 5, degree of A 8 okay 1, 2, 3, now let
us see which one has the highest degree. You see we have degree of A 7 is equal to 5, degree
of A 5 is equal to 6 okay so A 5 has the highest degree, so we have put A 5 in the in the 1st place
in the sequence.

Next comes A 3 okay, A 3 has degree 5 okay 1 lower than degree of A 5 so A 3 becomes next
and then A 7, A 7 also has the same degree we can write A 3, at the 2nd place we can write A 3 or
we can write A 7 because A 3 and A 7 have equal degrees. After A 7, A 1 has degree 4 okay so we
have A 1 then A 2, A 2 has degree 4 so we have A 2 then A 4 , A 4 has degree 4 so we have A 4
then A 6, A 6 has degree 3 and we have A 8, A 8 has degree 3 ok. Now, let us see how we shall
find the colors to these vertices okay. So we have arranged the vertices in the order of
decreasing degrees then we start with the 1st vertex A 5.

We assign color C 1 to A 5 ok so C 1 color you find to A 5 then A 5 is adjacent to A 3 okay so

then we leave it then A 5 is adjacent to A 7 so this also is left and then A 1. A 1 is here, A 5 is not
adjacent to A 1 so we assign C 1 color, now then let us say whether A 2 is adjacent to A 5 or not?
A 5 is adjacent to A 2 okay so we leave A 2 then A 4 , A 4 is adjacent to A 5 so we leave it, then
A 6, A 6 is adjacent to A 5 so we also leave it and then A 8, A 8 is also adjacent to A 5 so C 1 color
is given to A 5 and A 1 ok. Now we have completed one round that is from A 5 starting with A 5
to which we assign color C 1 , we have checked all the vertices in the sequence okay up to A 8.

Now we come back and start with A 3 ok, A 3 we assign color C 2 ok then A 3 you see let us see
A 7 is adjacent to it, so A 3 is here A 7 is here, A 3 is adjacent to A 7 ok they are joined okay so
A 7 is not adjacent to A 3 and therefore, we leave A 7 and then A 1 has already been assigned the
color A 2. Yeah A 2 is adjacent to A 3 so we leave it, A 4 , A 4 is not adjacent to A 3 so A 4 is
assigned color C 2 . And then A 6, A 6 is adjacent to A 3 so we leave it, A 8, A 8 is not adjacent to
A 3 so we give it color C 2 so A 8 is also given color C 2 . Now we have computed the color C 2 ,
we go back and start with A 7 .

A 7 is given color C 3 okay, A 7 is here okay A 7 is here. Now we have to see this one, this one,
this one, this one, yeah A 2, where is A 2? A 2 is not adjacent to A 7 so A 2 is given color C 3 ok.
And then what about A 6? A 6 is here, it is not adjacent to A 7 so it is also given color C 3 ok. So
A 5 and your A 1 they have color C 1 , they are colored with color C 1 , A 3 and then A 4 and then
A 8, they are colored with color C 2 , and then A 7, A 2 and then we have A 6 , they are colored
with color C 3 . So 3 colors are used to color all the vertices of this graph and we see that let us
now find the minimum number of colors to paint this graph ok.

We see that A 1, A 2, A 3 okay, A 1, A 2, A 3 are adjacent ok, A 1 is adjacent to A 2, A 2 is adjacent

to A 3 ok so they are to be painted with different color. So A 1, A 2, A 3 are to be painted with
different colors so there we will need 3 colors to paint A 1, A 2, A 3 consider A 5, A 7, A 8 ok A 5,
A 7, A 8 they are adjacent vertices ok A 5 is adjacent to A 7, A 5 is adjacent to A 8 so they will
have to be painted with different colors so 3 colors will be needed to paint A 5, A 7, A 8 with
different colors. So minimum here we have used 3 colors to paint the entire graph so
minimum number of colors needed to color this graph okay are 3, so that means chromatic
number is chromatic number of G is 3 which is the minimum number of colors to be used to
color the given graph, so 3 is the committing number here.
(Refer Slide Time: 9:50)

So this is the so thus we can say that this graph G is 3 color. If 3 colors are to be used to color
this graph then we say that it is free colorable. Now it is not two colorable as we have seen it
is not 2 colorable because A 1, A 2, A 3 they are adjacent, A 1 is adjacent to A 2, A 2 is adjacent to
A 3 so that means they are to be painted with different colors.

(Refer Slide Time: 10:23)

Now we have to consider the complete graphic A 6 okay, K 10, and in general we can take K n.
K n is complete graph, in the case of complete graph every vertex is adjacent to every other
vertex ok. So if vertices are V 1, V 2, V 3, V 4 , V 5, V 6 ok then each vertex is adjacent to every
other vertex that means they will all have to be painted with different colors okay so 6 colors
will be needed, 6 colors are required for painting K 6 ok. And similarly K 10, in the case of K 10,
10 colors will be required, 10 colors for coloring K 10. In general n colors are required and this
is the minimum number of colors okay X n equal to n here because it is a complete graph, you
cannot color this graph with less than n colors.

Now let us consider this graph okay, so here we are again use Welch Powell algorithm to
paint this graph and we shall find the chromatic number of G. So there are how many
vertices? 7 vertices so let us find the degree of V 1, you see 1, 2, 3, 4, 5 so it is 5, degree of V 2
is 1, 2, 3. Degree of V 3, degree of V 3 is 1, 2, 3, degree of V 4 , V 4 has got degree 1, 2, 3, 4,
degree of V 5 is 1 2 3 4, degree of V 6 is 1, 2, 3, 4, degree of V 7 is 1, 2, 3 ok.

Now let us write the vertices according to that degrees okay, so we have maximum degree is
5 okay so V 1 has the maximum degree okay so we have V 1 in order of decreasing degrees. So
then V 4 , V 5, V 6 they all have degree 4 ok so V 4 ,V 5, V 6, we can write in any order,V 4 ,V 5, V 6
because we all have same degrees ok and then we V 2, V 3, V 7, they all have degree 3 okay.

V 1 has degree by 5,V 4 , V 5, V 6 have degree for each and then V 2,V 3, V 7 have degree 3 ok.
Now so we color V 1 with C 1 color ok and let us see then which vertices are adjacent to V 1, so
V 1 is here V 1 is adjacent to V 5 ok V 1 is adjacent to V 5 so we leave V 5.V 6,V 1 is adjacent to
V 6 so we will leave V 6.V 4 ,V 1 is adjacent to V 4 ok, V 1 is adjacent to V 2 yes, V 1 is adjacent to
V 3 yes, V 1 is adjacent to V 7 no, so V 7 is also colored with C 1 ok.

Now we go to V 5 okay V 5 we color with C 2 now V 5 is here okay so V 5, V 6, where is V 6? V 6

is here soV 5 is not adjacent to V 6 so we give color C 2 to V 6. And then V 4 , V 4 is adjacent to
V 5 okay so we leave V 4 .V 2, V 2 is adjacent to V 5 so we leave V 2. Then V 3, V 3 is here ok V 3 is
not adjacent to V 5 soV 3 is also given color C 2 okay.

Then we come to V 4 okay, now we will give color C 3 to V 4 ok. V 4 is colored with C 3 and V 2
and very V 2? V 2 is here so V 4 is not adjacent to V 2 so V 2 is also colored with C 3 ok. So thus,
C 1 color is used for V 1 vertex, V 7 vertex, and C 2 color is used for coloring V 5, V 6 and V3,
and C 3 color is used to color V 4 and V 2 ok so 3 colors are required to paint this graph okay.

Now you see, V 1 is adjacent to V 4 , V 4 is adjacent to V 6, V 1 is adjacent to V 4 and V 4 is

adjacent to V 6 so V 1,V 4 , V 6 have to be painted with different colors and therefore 3 colors
will be required to paint the vertices of V 1, V 4 and V 6 so at least 3 colors have to be used but
here we have used 3 colors to paint the entire graph therefore, the chromatic number which is
the minimum number of colors to be used to paint the graph is χ (G) is equal to 3 okay, so the
chromatic number here is χ (G) is equal to 3.

(Refer Slide Time: 16:53)

Now let us consider this graph okay, so here let us see what is the degree of V 1? We have V 1,
V 2, V 3, V 4 , V 5, V 6 ok degree of V 1so 1, 2, 3, 4. Degree of V 2, degree of V 2 1, 2, 3. Degree of
V 3 so 1, 2, 3. Degree of V 4 is 1, 2, 3. Degree of V 5 so 1, 2, 3 and degree of V 6 is 1, 2, 3, 4 ok.
So there are 2 vertices V 1 and V 6 with the degree 4 each, we can write anyone at the 1st of the
sequence okay so we can write V 1, let us write V 1 then next is V 6, they both have equal
degrees then all others have 3 degrees each ok so we have V 2,V 3 ,V 4 , V 5.

Okay now we use color C 1 to paint V 1 vertex so for this we use C 1 color. Now V 6 is here, V 6
is not adjacent to V 1 so C 1 is used to paint V 6 okay. Then V 2, V 2 is adjacent to V 1 ok so we
leave this,V 3 is also adjacent to V 1 so leave this, V 4 is adjacent to V 1 so leave it, V 5 is
adjacent to V 1 so leave it ok so V 1, V 6 are painted with C 1 color.

Now, we go to V 2 and paint it with C 2 color and then V 2, V 2 is here, V 2 and V 3 they are not
adjacent okay so C 2 color is used for V 3 also ok. And then V 2 is adjacent to V 4 , V 2 is not
adjacent to V 5, no V 2 is not adjacent to V 5, V 5 is here, so this is also painted with C 2 color ok,
and then what is left? Then we are left with V 4 ok, V 4 is painted with color C 3 ok. So C 1
color is used for V 1 , V 6, C 2 color is used for V 2 , V 3 and V 5 and C 3 color is used for V 4 ok,
so 3 colors are used to paint the vertices here.

Now, let us see what is the chromatic number, you see we have V 1, V 2, V 1 is adjacent to V 2,
V 1 is adjacent to V 5 okay so 3 colors will be needed to paint V 1,V 2, V 5 okay and here we
have used 3 colors to paint the entire graph. Chromatic number means minimum number of
colors to be used to paint the graph so χ (G) is equal to 3, we cannot paint the graph with
colors less than 3 because V 1, and V 5, V 1 is adjacent to V 2 and V 1 is adjacent to V 5.

(Refer Slide Time: 20:31)

Now, let us consider this graph, ok so use the Welsh Powell algorithm here, so degree of V 1,
what is degree of V 1? 1, 2, 3 degree of V 1 is 3. Degree of V 2 okay, degree of V 2 is how much;
1, 2, 3. Degree of V 3 is 1, 2, 3. Degree of V 4 1, 2, 3 and degree of V 5 1, 2, 3 and degree of V 6
1, 2, 3 ok so they all have degrees 3 each okay soV 1, V 2,V 3,V 4 , V 5, V 6. Here, let us start with
V 1, we can color it with C 1 color, now V 1 is adjacent to V 2 so we have to leave V 2, then V 1 is
adjacent to V 3 so leave V 3, V 1 is adjacent to V 4 , no so V 4 can be colored with C 1 . V 1 is
adjacent to V 5, yes, V 1 is adjacent to V 5 so we cannot color V 5 with C 1 . V 1 is not adjacent to
V 6 so we can color it with C 1 color okay.

Then we go to V 2, V 2 can be colored with C 2 then V 2 is adjacent to V 3 no, so it can also be

colored withC 2 . And then V 2, is it adjacent to V 5? V 2 is not adjacent to V 5 so it can be
colored with C 2 ok. So, C 1 color is used to paint V 1, V 4 and V 6 okay, and C 2 color can be
used for V 2, V 3 and V 5 so 2 colors are required. And you see we have V 1 and V 2, they are
adjacent to each other so we will have to use different colors to paint V 1 and V 2 so 2 colors
are needed for painting V 1 and V 2 and here we are using 2 colors to paint the entire graph so
minimum number of colors used to paint this crap that is chromatic number is 2. So that is the
end of this, thank you very much for your attention.