>> Can you tell if computing the clique number of those graphs is
>> painful, and if it helps computer the chromatic number faster?
>
> No I guess I can just use the custom ILP program. I just wanted to point
> this up just because I thought it may make sense to change it at some point
>From your
On Monday, 31 August 2015 18:05:10 UTC+2, Nathann Cohen wrote:
>
> > I am doing 8-regular graphs of order 1000 so they have large
> indepdendent
> > sets and Sage actually gets stuck in computing their Independence number
> =)
> > On the other hand CPLEX finds the chromatic number within a fe
Sage can compute Lovasz theta for you, although it is not too fast now.
Can you try this for your graphs?
(this gives you a lower bound on the chromatic number, as you know)
On Monday, 31 August 2015 08:40:15 UTC-7, Jernej Azarija wrote:
>
>
>
> On Monday, 31 August 2015 15:55:33 UTC+2, Nathann C
> I am doing 8-regular graphs of order 1000 so they have large indepdendent
> sets and Sage actually gets stuck in computing their Independence number =)
> On the other hand CPLEX finds the chromatic number within a few minutes.
Can you tell if computing the clique number of those graphs is
painfu
On Monday, 31 August 2015 15:55:33 UTC+2, Nathann Cohen wrote:
>
> So I am wondering - does it actually make sense to compute the clique
>> number and independent set of a graph that is very large and sparse (say
>> 8-regular graph on 1k vertices?)
>>
>> Computing the chromatic number on my in
>
> So I am wondering - does it actually make sense to compute the clique
> number and independent set of a graph that is very large and sparse (say
> 8-regular graph on 1k vertices?)
>
> Computing the chromatic number on my instances using a ILP directly takes
> 5 minutes while the current Sa
