Message Boards Message Boards

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 ?
POSTED BY: Reinaldo Giudici
Answer
4 years ago
Could you provide an example of each?
POSTED BY: Bruce Miller
Answer
4 years ago
Example where does not work
In this example does not work the Chromatic Polynomial
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}})]
POSTED BY: Reinaldo Giudici
Answer
4 years ago
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.
POSTED BY: Sam Carrettie
Answer
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}}
POSTED BY: Reinaldo Giudici
Answer
4 years ago
Hi Reinaldo:

Did you look at the function ChromaticPolynomial ? it is from the Combinatorica package.
POSTED BY: Sander Huisman
Answer
4 years ago
Dear Sander, Yes I did it
my 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]
POSTED BY: Reinaldo Giudici
Answer
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.
POSTED BY: Sander Huisman
Answer
4 years ago
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^12

FromAdjacencyMatrix[m] // ShowGraph

POSTED BY: Vitaliy Kaurov
Answer
4 years ago
Dear Vitaly Kaurov
Your suggestion works pretty good. I am happy and I am continuing my research.
Thanks a lot,
Reinaldo Giudici
POSTED BY: Updating Name
Answer
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 // ShowLabeledGraph


The graph is shown but the contract graph no
Contract[g, {1, 2}]

Thanks a lot in advance,
Your sincerely

Reinaldo Giudici
POSTED BY: Reinaldo Giudici
Answer
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/)

POSTED BY: Allan Zea
Answer
4 months ago
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.
POSTED BY: Moderation Team
Answer
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 sincerely

Reinaldo Giudici
POSTED BY: Updating Name
Answer
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 sincerely
Reinaldo Giudici
POSTED BY: Reinaldo Giudici
Answer
4 years ago
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}};

In[] = ChromaticPolynomial[FromAdjacencyMatrix[m], z]

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 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 sincerely
Reinaldo Giudici
POSTED BY: Reinaldo Giudici
Answer
4 years ago
you need to convert h to combinatorica graph like you did for chromatic polynomial:
Contract[FromAdjacencyMatrix[h], {1, 2}]
POSTED BY: Jaebum Jung
Answer
4 years ago
Dear Jaebum, 
I have already done as I did for chromatical polynonial and did not work as I show you:
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}};
Contract[FromAdjacencyMatrix[h], {1, 2}]
Graph : < 17, 11, Undirected >

that the answer I GOT
POSTED BY: Reinaldo Giudici
Answer
3 years ago

Group Abstract Group Abstract