in Graph Theory edited by
1,577 views
4 votes
4 votes

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?

in Graph Theory edited by
1.6k views

4 Comments

@Ayush Upadhyaya 

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

0
0

@Gyanu-Refer Narsingh Deo

0
0

@Ayush Upadhyaya

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

Now what will be equation?

0
0

2 Answers

0 votes
0 votes

$\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

0 votes
0 votes

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, 3rd vertex have 2c1 ways and the 4th 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

Related questions