# Chromatic polynomials for custom graphs

GROUPS:
 1 ) How to use the math functions over graphs that are not in the data graph of Mathematica?2 ) How to compute Chromatic Poynomials for a graph introduced by myself ?
4 years ago
19 Replies
 Bruce Miller 1 Vote Could you provide an example of each?
4 years ago
 Example where does not workIn this example does not work the Chromatic PolynomialAdjacencyGraph[({{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0,     0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0,    0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1,    0, 0}, {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0,     0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0,    1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0,    0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0,     0, 0, 1, 0}})]
4 years ago
 Sam Carrettie 1 Vote Bruce is right, it is not at all clear what do you need. Please give details and example. Also take a look at this MathWorld article. There is a link to an attached Mathematica notebook with code right below the tittle of the page.
4 years ago
 I need the Chromatic Polynomial of graph defined by the following matrix, may you give the pass to get it.Sincerely, Reinaldo Giudici {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},  {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1},  {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},  {0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0},  {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0},  {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},  {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0},  {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0},  {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}}
4 years ago
 Hi Reinaldo:Did you look at the function ChromaticPolynomial ? it is from the Combinatorica package.
4 years ago
 Dear Sander, Yes I did itmy example:In this example does not work the Chromatic Polynomial g = AdjacencyGraph[({{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0,      0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0,      0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1,      0, 0}, {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0,      0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0,      1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0,      0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0,      0, 0, 1, 0}})] ChromaticPolynomial[g]
4 years ago
 This uses the old Graph specification, all from the combinatorica package:You probably have to use FromAdjacencyMatrix, and related functions from:Combinatorica/guide/GraphConstructionAndRepresentations^^ Look that up in the help.
4 years ago
 Vitaliy Kaurov 1 Vote Could you please read carefully about package usage in Mathematica and especially this tutorial: Combinatorica. Please note Combinatorica package functionality is being in the process of transfer to built in Graph functionality. But do not confuse their syntax - they do not match.It all works: << Combinatorica`   m = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},   {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1},   {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1},   {0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0},   {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0},   {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},   {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0},  {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0},  {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};In[] = ChromaticPolynomial[FromAdjacencyMatrix[m], z]Out[] = -3210 z + 13675 z^2 - 26877 z^3 + 32819 z^4 - 28015 z^5 + 17680 z^6 - 8444 z^7 + 3052 z^8 - 816 z^9 + 153 z^10 - 18 z^11 + z^12FromAdjacencyMatrix[m] // ShowGraph
4 years ago
 Dear Vitaly KaurovYour suggestion works pretty good. I am happy and I am continuing my research.Thanks a lot,Reinaldo Giudici
4 years ago
 Dear Vitaly Kaurov,I have been working on graphs up to 16 vertices and the program to compute  works fine (it takes about  5 hours on my  Sony Laptop), however when I try a graph with 18 vertices does not work, ever after 26 hours (I aborted de computations). For intance, the following graph :g= {{0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 0,   0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1,   0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,   0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0,   0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {0,   1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0,   0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0,   0, 0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,   0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,   1}, {0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0,   0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0,   1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1,   0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,   1, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   1}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}};Another question, the comand Constraction Contract[g,{x,y}]is not working for us, or I do not how to used it.g = {{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0,     0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 1,     0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,     0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0,     0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0,     0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0,     0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}}; FromAdjacencyMatrix // ShowLabeledGraphThe graph is shown but the contract graph noContract[g, {1, 2}]Thanks a lot in advance,Your sincerelyReinaldo Giudici
4 years ago
 Dear Reinaldo,Chromatic polynomials are typically calculated using a deletion-contraction recursion, which is a very lengthy and awkward procedure to perform. The problem of computing such polynomials (which are a specialization of the Tutte polynomial) is $\#P$-hard in general, so one can not expect miracles of the "d-c" recursion, which I assume is the built-in method of Combinatorica.Determinining whether a graph admits a $k$-coloring is known to be $NP$-complete for $k\geq 3$, but there exist various approximation algorithms for performing graph colorings that are somewhat optimal. In [1], Bonnie Berger and John Rompel developed an algorithm with a performance guarantee of $O(n(log~log~n)^3/(log~n)^3)$ and Magnús Halldórsson improved this result to $O(n(log~log~n)^2/(log~n)^3)$ in [2].In 2009, a research group from New Zealand calculated the Tutte polynomial of the truncated icosahedron and, as their website explains, this took about one week to compute in a cluster of 150 computers [3]. So yes, computing the chromatic polynomial (more generally Tutte polynomial) of large graphs can be a complete nightmare as you already experienced. This is probably why finding efficient coloring algorithms remains one of the most exciting open challenges in combinatorics and computer science.I hope this helps!References:[1] B. Berger and J. Rompel. A better performance guarantee for approximate graph coloring. Algorithmica, 1988.[2] M. M. Halldórsson. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 1993.[3] "Code for Computing Tutte Polynomials" (http://homepages.ecs.vuw.ac.nz/~djp/tutte/)
1 year ago
 Oleg Bayborodin 1 Vote I don't think that the chromatic polynomials functionality of Mathematica and the cited 2009 paper define the possible limits for performance. See for example https://www.hackerrank.com/contests/projecteuler/challenges/euler194 and specifically the constraints on the graph size. It implies that with proper optimization techniques the chromatic polynomials for planar graphs up to 60 vertices can be calculated within seconds.
5 months ago
 Dear Oleg,Thank you very much for your response and the interesting PE problem.What really defines the limits for performance is the fact that the running time of the deletion-contraction algorithm that is normally used to compute the Tutte - and chromatic - polynomial is $O((\frac{1+\sqrt{5}}{2})^{n+m})$ for a graph on $n$ vertices and $m$ edges (See Chapter 2 of [1]). This recursion is most probably the calculation method in Combinatorica.It has been found that evaluating the Tutte polynomial is $\#P$-hard at any point $(a,b)$ except when $(a,b)$ lies on the hyperbola $H_1:=(x-1)(y-1)=1$ and eight special points [2]. In such cases the computation can be done in polynomial time. The Tutte polynomial of any planar graph along the special hyperbola $H_2:=(x-1)(y-1)=2$ can also be computed in polynomial time; maybe this is the case in the problem you mention.Best regards,AllanReferences:[1] H. S. Wilf, Algorithms and complexity, vol. 986, Prentice-Hall Englewood Cliffs, NJ, 1986.[2] F. Jaeger, D. L. Vertigan, D. J. Welsh, On the computational complexity of the Jones and Tutte polynomials, in: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 108, Cambridge University Press, 35–53, 1990.
5 months ago
 Moderation Team 1 Vote Dear Reinaldo, please take a few minutes to learn how to make proper posts with this tutorial:How to type up a post: editor tutorial & general tips- especially posting code. You can see other people on the thread use proper tools for posting code. It seems that because you pasted code as plain text some parts of it are missing.
4 years ago
 Dear Vitaly Kaurov, I have been working on graphs up to 16 vertices and the program to compute works fine (it takes about 5 hours on my Sony Laptop), however when I try a graph with 18 vertices does not work, ever after 26 hours (I aborted de computations). For intance, the following graph : g={{0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 0,    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 1,    0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,    0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0,    0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {0,    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0,    0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 0,    0, 0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0,    0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,   1}, {0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0,   0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0,   1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 1,   0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,   1, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   1}, {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}};ChromaticPolynomial[FromAdjacencyMatrix[g], z]Another question, the Combinatorica command Contract[g,{x,y}] is not working for us, or I do not how to used it.h={{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 1,0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};The graph is shown but the contract graph no Contract[g, {1, 2}]We tried to enter the matrix for the suggested method, but had no luck.Thanks a lot in advance,Your sincerelyReinaldo Giudici
4 years ago
 Another question, the command  Contract[g,{x,y}]i  s not working for us, or I do not how to used it.h={{0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 1,0, 0, 0, 1, 0, 0, 0}, {1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {1, 0,0, 0, 0, 0, 0, 1, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0}};The graph is shown but the contract graph Contract[h, {1, 2}]We tried to enter the matrix for the suggested method, but had no luck.Thanks a lot in advance,Your sincerelyReinaldo Giudici