Dear Alireza, On 02 Apr 2007, at 17:26, Alireza Abdollahi wrote:
Dears I would like to know whether anyone has implemented a program under GAP/GRAPE to 1) calculate the Cromatic Number of a graph?
Apparently there is no implementation of this, though this might be feasible.
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.
You can construct the Caley graph of G for a specified generating set S with the GRAPE package or with the HAP package. But enumerating ALL generating sets for a finite group would be hard, so if you will write such a program, the order of the groups that it will be capable to deal with will be limited. Best wishes, Alexander
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 AbdollahiI 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
_______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
