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

Dark Mode

1,577 views

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?

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

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