
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
August 29th, 2014, 02:23 PM  #1 
Newbie Joined: Aug 2014 From: Spain Posts: 4 Thanks: 0  How many ways are there to color this graph with the following constraints? How many ways are there to color this graph with the following constraints? We have three colors: blue, red, green, and we require that the number of nodes of color green is 2, and blue 2, and red 2  the same number. And here is my attempt: Automorphisms: $$(1)(2)(3)(4)(5)(6)$$ $$(34)(1)(2)(5)(6)$$ $$(56)(1)(2)(3)(4) $$ $$(34)(56)(1)(2)$$ $$(12)(35)(46)$$ $$(12)(36)(45)$$ Cycle index of group: $$Z_G(x_1,...,x_6) =\frac16 (x_1^6 + 2x_2^3 + 2x_2x_1^4 + x_2^2x_1^2) $$ And using PĆ³lya theorem we get generating function: $$U_D(g,r,b) = Z_G(g+r+b, g^2+r^2+b^2, ...,g^6+r^6+b^6) = \\ \frac16 ((g+r+b)^6 + 2(g^2+r^2+b^2)^3 + 2(g^2+r^2+b^2)(g+r+b)^4 + (g^2+r^2+b^2)^2(g+r+b)^2)$$ And coefficient with $r^2g^2b^2$ is $\frac16 (90 + 12 +0 + 0 ) = 17$ Is it solution correct? 

Tags 
color, constraints, graph, ways 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How many ways are there to color the Hshaped tree with 3 colors such that each c  xawey  Abstract Algebra  2  August 29th, 2014 08:11 PM 
eigenvectors Constraints  de1  Linear Algebra  0  August 4th, 2014 08:54 AM 
Number of ways to make a graph from nsize vertex set  Singularity  Applied Math  1  April 15th, 2011 07:42 AM 