881 views

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 _________.

post it

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} ?

### 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...

1
1,578 views
2
849 views
3
856 views
1 vote