Dears I would like to know whether anyone has implemented a program under GAP/GRAPE to
1) calculate the Cromatic Number of a graph? 2) produce all connected Cayley graphs of a finite group, i.e., given a finite group G, find all generating sets S of G and then construct the Cayley graph of G with respect to S, for all S. For (1) in GRAPE, there is a function (VertexColouring) which finds only a *proper vertex colouring* for a given graph. The size of this proper vertex colouring is not necessarily equal to the cromtic number. Thanks in advance for any help. All the Best Alireza Abdollahi > I used the VertexColouring function in GRAPE and (I > think) I have no > problem with it; but I would like to know whether it > is possible to get > the chromatic number of a graph. > > In particular in the following example I think the > function gives only > a *proper vertex colouring* not a one with the > mininum number of > colours. > > D:=Group([ (1,2,4,7,5,6,3), (2,4,5)(3,6,7), (8,9) ]) > C:=CayleyGraph(D,[(8,9)(1,2,4,7,5,6,3),(2,4,5)(3,6,7)]); > eC:=EdgeGraph(C);; > VertexColouring(eC); > [ 1, 3, 2, 4, 1, 3, 4, 5, 2, 3, 5, 2, 3, 4, 4, 1, 5, > 1, 3, 1, 2, 3, 1, 4, 2, > 5, 4, 2, 4, 5, 4, 3, 4, 3, 3, 2, 4, 3, 2, 1, 1, > 2, 1, 2, 5, 4, 4, 5, 2, 3, > 5, 2, 3, 4, 1, 4, 1, 4, 2, 5, 1, 2, 1, 2, 3, 3, > 1, 4, 5, 4, 3, 1, 5, 3, 1, > 4, 2, 2, 3, 2, 3, 2, 1, 1 ] > > > I think, there is a proper vertex colouring > for the graph "eC" with 4 colours. Can I check this > claim by GRAPE? > Is there a function in GRAPE to compute the > chromatic number? > > Thanks in advance. > > All the Best > > Alireza Abdollahi > > > > > > > > ---------------------------------------------------------------- > University of Isfahan (http://www.ui.ac.ir) > > Alireza Abdollahi Department of Mathematics University of Isfahan, Isfahan 81746-73441,Iran e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] URL: http://sci.ui.ac.ir/math/New/abdollahi.htm ____________________________________________________________________________________ Expecting? Get great news right away with email Auto-Check. Try the Yahoo! Mail Beta. http://advision.webevents.yahoo.com/mailbeta/newmail_tools.html _______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
