Mathematica Notebook accompanying the article “M. Gerling: Bivariate Chromatic Polynomials in Computer Algebra”

SetDirectory["..."]

<<BivariatePolynomials.m

To compute the first example for Theorem 11, we first define the given graph.

ShowGraph[G1=DeleteEdges[Combinatorica`CompleteGraph[9],{{1,2},{1,3},{1,4},{5,6},{5,7},{8,9}}]]

To compute the bivariate chromatic polynomial for this graph, we use the implementation "BivariatePolynomialAGM1" of the recursion formula (AGM1) for a graph G by Averbouch, Godlin and Makowsky from Theorem 6. As we see, this method needs some minutes on a PC.

Timing[BivariatePolynomialAGM1[G1,x,y]]

Now, we use the implementation "BivariatePolynomialAGM2" for the same recursion formula (AGM2), which solves the equation for the graph G - e instead of G with an edge e from E. For our graph, this is much faster than the implementation "BivariatePolynomialAGM1".

Timing[BivariatePolynomialAGM2[G1,x,y]]

Our equation from Theorem 11 is implemented directly and is clearly more efficient than the implementation "BivariatePolynomialAGM1".

Timing[Expand[Sum[Binomial[1,c]*3^c*Sum[Binomial[1,b]*2^b*Sum[Binomial[1,a]*1^a*Sum[Binomial[9-2*c-2*b-2*a,i]*(x-y)^i*FunctionExpand[FactorialPower[y,9-c-b-a-i]],{i,0,9-2*c-2*b-2*a}],{a,0,1}],{b,0,1}],{c,0,1}]]]

Now we consider the second example for Theorem 11. Because of the graph' s size we define the graph without showing it.

G2=DeleteEdges[Combinatorica`CompleteGraph[40],{{1,2},{1,3},{1,4},{1,5},{1,6},{7,8},{7,9},{7,10},{7,11},{12,13},{12,14},{12,15},{12,16},{17,18},{17,19},{17,20},{21,22},{23,24},{25,26},{27,28}}];

In this case we use only the implementation "BivariatePolynomialAGM2", because it is more efficient for the graph G2. But even this recursion cannot compute the bivariate chromatic polynomial in less than one hour.

TimeConstrained[BivariatePolynomialAGM2[G2,x,y],3600]

Our equation from Theorem 11 can solve this problem easily. However, the output is very large.

Timing[Expand[
Sum[Binomial[1,e]*5^e*
Sum[Binomial[2,d]*4^d*Sum[Binomial[1,c]*3^c*Sum[Binomial[0,b]*2^b*Sum[Binomial[4,a]*1^a*Sum[Binomial[40-2*e-2*d-2*c-2*b-2*a,i]*(x-y)^i*FunctionExpand[FactorialPower[y,40-e-d-c-b-a-i]],{i,0,40-2*e-2*d-2*c-2*b-2*a}],{a,0,4}],{b,0,0}],{c,0,1}],{d,0,2}],{e,0,1}]]]

We turn to the first example for Theorem 13.

ShowGraph[G3=CompleteKPartiteGraph[2,2,2,2]]

As above, we first compute the bivariate chromatic polynomial by the implementation "BivariatePolynomialAGM1".

Timing[BivariatePolynomialAGM1[G3,x,y]]

The implemenation "BivariatePolynomialAGM2" needs less time to compute the same polynomial.

Timing[BivariatePolynomialAGM2[G3,x,y]]

Our own equation from Theorem 13 needs less time than the implementation "BivariatePolynomialAGM1".

Timing[Expand[Sum[Binomial[4,i]*Sum[Binomial[8-2*i,l]*(x-y)^(8-2*i-l)*FunctionExpand[FactorialPower[y,i+l]],{l,0,8-2*i}],{i,0,4}]]]

The second example for Theorem 13 is a large graph, so we don' t depict it.

ShowGraph[G4=CompleteKPartiteGraph[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]];

We see that not even the implementation "BivariatePolynomialAGM2", which is much more advantageous for this graph, can compute the bivariate chromatic polynomial in less than one hour.

TimeConstrained[BivariatePolynomialAGM2[G4,x,y];,3600]

The formula from Theorem 13 can do the computation in few seconds. However, the output is very large.

Timing[Expand[Sum[Binomial[30,i]*Sum[Binomial[60-2*i,l]*(x-y)^(60-2*i-l)*FunctionExpand[FactorialPower[y,i+l]],{l,0,60-2*i}],{i,0,30}]]]

The first example for Theorem 14 is given by the graph below.

ShowGraph[G5=CompleteKPartiteGraph[3,3,3]]

Similar to the results for the last two examples, the implementation "BivariatePolynomialAGM1" computes the polynomial very slowly, althought the graph is not large.

Timing[BivariatePolynomialAGM1[G5,x,y]]

The implementation "BivariatePolynomialAGM2" is again much faster.

Timing[BivariatePolynomialAGM2[G5,x,y]]

The most advantageous method is our equation from Theorem 14.

Timing[Expand[Sum[Binomial[3,i]*Sum[Binomial[i,t]*3^(i-t)*Sum[Binomial[9-2 i-t,l]*(x-y)^(9-2 i-t-l)*FunctionExpand[FactorialPower[y,i+l]],{l,0,9-2 i-t}],{t,0,i}],{i,0,3}]]]

As a second example we choose the graph below.

G6=CompleteKPartiteGraph[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3];

Again, even the implementation "BivariatePolynomialAGM2" has a too long running time.

TimeConstrained[BivariatePolynomialAGM2[G6,x,y];,3600]

Our formula from Theorem 14 comes to a result after about 1 minute.

Timing[Expand[Sum[Binomial[20,i]*Sum[Binomial[i,t]*3^(i-t)*Sum[Binomial[60-2 i-t,l]*(x-y)^(60-2 i-t-l)*FunctionExpand[FactorialPower[y,i+l]],{l,0,60-2 i-t}],{t,0,i}],{i,0,20}]]]

We finish our considerations with two examples for Theorem 15. The first example graph is given as follows.

ShowGraph[G7=CompleteKPartiteGraph[3,3,3]]

The implementation "BivariatePolynomialAGM1" is again slow.

Timing[BivariatePolynomialAGM1[G7,x,y]]

A shorter running time is possible by using the implementation "BivariatePolynomialAGM2".

Timing[BivariatePolynomialAGM2[G7,x,y]]

Our equation from Theorem 15 is very fast again for this polynomial.

Timing[Expand[BivariatePolynomialGerling[3,3,x,y]]]

Finally, we give a last example for Theorem 15.

G8=CompleteKPartiteGraph[10,10,10,10];

The implementation "BivariatePolynomialAGM1" cannot compute the bivariate chromatic polynomial with less than one hour running time.

TimeConstrained[BivariatePolynomialAGM1[G8,x,y];,3600]

By using the implementation "BivariatePolynomialAGM2" the polynomial cannot be computed in less than an hour either.

TimeConstrained[BivariatePolynomialAGM2[G8,x,y];,3600]

Althought our formula from Theorem 15 needs a lot of time, it comes to a result.

Timing[Expand[BivariatePolynomialGerling[10,4,x,y]]]