3 votes 3 votes A vertex colouring with four colours of a graph G = (V, E) is a mapping V → {R, G, B, Y }. So that any two adjacent vertices does not same colour. Consider the below graphs: The number of vertex colouring possible with 4 colours are _________. Graph Theory graph-theory graph-coloring + – srestha asked Sep 21, 2018 srestha 1.5k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Shaik Masthan commented Sep 21, 2018 reply Follow Share i am getting, 4!*(3*2*2*1) = 24*12 =288 what is the answer? 0 votes 0 votes srestha commented Sep 21, 2018 reply Follow Share no ,not matching :( but can u explain? 0 votes 0 votes Shaik Masthan commented Sep 21, 2018 reply Follow Share i realized, i miss some of the combinations, i will conclude it, need some more time 0 votes 0 votes aambazinga commented Sep 21, 2018 reply Follow Share i'm getting 4!*34=816. 0 votes 0 votes srestha commented Sep 21, 2018 reply Follow Share no.., but explain plz 0 votes 0 votes Magma commented Sep 21, 2018 reply Follow Share https://math.stackexchange.com/questions/2496188/number-of-ways-to-color-this-graph 3 votes 3 votes Shaik Masthan commented Sep 21, 2018 reply Follow Share @Magma it's too bad, for providing the link... i tried and got the answer, when i want to post, you gave the link.. but the link have better approach than me. 0 votes 0 votes Magma commented Sep 21, 2018 reply Follow Share Shaik Masthan what's your approach ?? post it 0 votes 0 votes srestha commented Sep 23, 2018 reply Follow Share 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 votes 0 votes Shaik Masthan commented Sep 24, 2018 reply Follow Share i added my answer, check it 0 votes 0 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes for clarity images https://drive.google.com/open?id=1iqmqoKewUfQzQMFHB99IVXDokSLlBwgy Shaik Masthan answered Sep 24, 2018 selected Sep 24, 2018 by srestha Shaik Masthan comment Share Follow See 1 comment See all 1 1 comment reply chirudeepnamini commented Oct 28, 2019 reply Follow Share @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 votes 0 votes Please log in or register to add a comment.