[GAP Forum] GRAPE

[Alireza Abdollahi]

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: abdollahi at member.ams.org
        a.abdollahi at math.ui.ac.ir
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