Group Abstract Group Abstract

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
1 year ago
Could you provide an example of each?
POSTED BY: Bruce Miller
Answer
1 year 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
1 year 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
1 year 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
1 year ago
Hi Reinaldo:

Did you look at the function ChromaticPolynomial ? it is from the Combinatorica package.
POSTED BY: Sander Huisman
Answer
1 year 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
1 year 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
1 year 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
1 year 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
1 year 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
1 year 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
1 year 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
1 year 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
1 year 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
1 year 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
1 year 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
1 year ago