[GAP Forum] GRAPE

[Alexander Konovalov]

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 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