Graph Coloring

Question

How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ?
There is a condition that adjacent vertices should not be of the same color
I am getting $1680$. Is it correct?

Comments

here we also can color with 3 colors

But that is not satisfying the question

right?

Only for 4 color we need to ans

---

why not with 3 colors?

---

no , they specified strictly 4 colors

---

Shaik Masthan i'm sure this is balaji's self made question and he is curious to know with exactly 4 colors :p

---

it will be $\binom{7}{4}\left ( \binom{5}{1}\times \binom{2}{1}\times \binom{2}{2}+\binom{5}{1}\times \binom{2}{2}\times \binom{2}{1} \right )$

---

@Mk Utkarsh

haha , but good one :)

---

I am getting 1260

Since we are selecting any 4 colors out of 7, we can do that in $7\choose 4$ ways.

We have 5 nodes, and 4 colors. 1 color will repeat.

Let nodes be A,B,C,D,E. Usual top to bottom left to right naming. (D will be the one with degree 2)

If A takes repeating color, B,C,e cannot take that color. Thus, D is fixed. For rest 3, we have 3! ways.

similarly, for B,C,E we have 3! ways.

If D takes repeating color, only B and E cannot take repeating color leaving repeating color choice between A and C. Hence 2*3! (rest can be placed any way)

So total it comes 1260

Please correct if the approach is wrong

---

 

This is the original question and this is the answer I got 3!*2 * XC3 + 4!*3 *XC4 + 5! * XC5

---

Correct answer is 2520.

Case 1-

in above graph all 4(A,B,C and E) vertices are assigned with 4 different colors but now vertex D have 2 choices either it can be assigned with color of vertex C or A.

from the range of {1,2,3......,r} to assign maximum 4 colors to this graph number of ways are = 2 * r(r-1)(r-2)(r-3) 

here r =7 then = 1680 ways.

EDIT-

Case 2-

I missed one scenario that when vertices(A,C,E and D) are colored 4 different color then vertex B can also be assigned with color of E.

then total ways = Case 1 + Case 2 = 1680 + 840 = 2520

 

---

@Shubhgupta No, It is wrong. The correct answer will be 2520

---

please give scenario which missed in my case. because 2520 will be the answer when you will asked how many ways are there to color it with 5 color that are = r(r-1)(r-2)(r-3)(r-4) = 2520

---

CREDITS : Facebook User Gaurav Tank

---

got my mistake thanks.. :). I have corrected my comment.

---

2520 should be the correct one :)

---

@Balaji Jegan

why 4! is needed?

is arrangement making any difference?

---

Yes, arrangement does make difference

---

So ans 105?

---

2520 is right

---

Best way is to form chromatic polynomial of this graph and then answer can be given for any number of colors quickly.

---

@Ayush Upadhyaya

can you upload answer as per your approach ?

---

@Ayush Upadhyaya 

sir how to write a chromatic polynomial for any graph.  Give me some useful link. 

---

@Gyanu-Refer Narsingh Deo

---

@Ayush Upadhyaya

chromatic polynomial is $\sum_{I=1}^{n}c_{i}\binom{\lambda }{i}$ right?

Now what will be equation?

Answer 1

$\rightarrow$ Its a simple combinatorics problem.

$\rightarrow$ We are given $7$ colors and we can use any of the $4$ colors.

$\rightarrow$ So we can select $4$ colors out of $7$ colors in $^7 C_4$ ways = $35$ ways

$\rightarrow$ After selecting $4$ colors just start checking the ways of assigning colors to each node.

$\rightarrow$ I have started from nodes $A$ then $B$ then $C$ then $D$ and at last $E$ (You can follow any order)

$\therefore$ Total ways of coloring the Graph = $35 *4*3*2*3*1$ ways = $2520$ ways

Answer 2

Let’s choose 4 colors from 7 in 7C4 ways.

Now out of the 4 choosen colors,  the 1st vertex can have 4c1 ways, 2nd vertex have 3c1, 3^rd vertex have 2c1 ways and the 4^th will have 1c1 ways.

Mathematically we can write this as 7c4*4c1*3c1*2c1.

But since in the question “” There is a condition that adjacent vertices should not be of the same color”

The chromatic number of the graph is 5

So the final vertex needs to assigned with different color. So among the remaing 3 colors we can do it in 3c1 waYS. 

So the final eq becomes 7c4*4c1*3c1*2c1*3c1=2520