in Graph Theory
881 views
2 votes
2 votes

A vertex colouring with four colours of a graph G = (VE) is a mapping V → {RGBY }. So that any two adjacent vertices does not same colour. Consider the below graphs:

The number of vertex colouring possible with 4 colours are _________.

in Graph Theory
by
881 views

4 Comments

Shaik Masthan  

what's your approach ??

post it

0
0

chk this one

Type 4: A and C are equally colored f or . There are 22 colorings of this type. Assume A↦f, C↦f. This allows of B↦{e,g,h}, D↦{e,h}. Makes 1212 in total.

why not taken D->{e,f,h} ?

0
0
i added my answer, check it
0
0

1 Answer

6 votes
6 votes
Best answer
selected by

1 comment

@Shaik Masthan

i have a approach and i need your help...my approach is as follows 

​​​​​​{{a,g,c},{b,e,d},{f},{h}} be a set of independent sets whose union is all the vertices of graph. we have 4!=24 ways to color one set of independent sets.4 ways to color {a,g,c},3 ways to color {b,e,d},2 ways to color {f}, 1 way to color {h}.

One more such set is {{a,h},{b,e,d},{,c,f},{g}} whose union is all vertices of graph. We have 24 ways to ways to color one set of independent sets.

but my problem is how to find the number of such sets. I need your help here...

0
0

Related questions