My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
August 29th, 2014, 01: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?
xawey is offline  
 
Reply

  My Math Forum > College Math Forum > Abstract Algebra

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 07:11 PM
eigenvectors Constraints de1 Linear Algebra 0 August 4th, 2014 07:54 AM
Number of ways to make a graph from n-size vertex set Singularity Applied Math 1 April 15th, 2011 06:42 AM





Copyright © 2018 My Math Forum. All rights reserved.