1
$\begingroup$

I have a graph with $n$ verices, and I want to compute the number of ways to color the graph (with no adjacent vertices having the same color) using anywhere between $1$ and $n$ colors. This number (including permutations of colors) should be given by the chromatic polynomial for the graph.

However, I would like to present this number as a fraction of all possible ways to color the graph (without a restriction on not coloring adjacent vertices with the same color). The number of unique ways to do this for any $k<=n$ is $k$ multichoose $n$, or $(k+n-1)$ choose $n$.

The issue then is that the chromatic polynomial counts color permutations, whereas the multiset does not.

How do we place these on equivalent terms? In other words, how to we exclude color permutations from the chromatic polynomial or incorporate color permutations into the multichoose number?

$\endgroup$
0
$\begingroup$

The number of ways to color the vertices of a labelled graph on $n$ vertices if there are $k$ colors available is $k^n$. Thus if the graph has chromatic polynomial $f$ then the probability a random coloration where there are $k$ colors available is $\dfrac{f(k)}{k^n}$

$\endgroup$
  • $\begingroup$ Yes, of course, thank you @Bananarama! Is there a way to account for graph symmetry - in other words, some of the $k^n$ possibilities will be identical under the graph symmetry (for example, octahedral symmetry)? $\endgroup$ – user156167 Jun 9 '14 at 21:04
  • $\begingroup$ It depends on the graph in question, there are various things you have to take into account, and then adjust both the chromatic function and the denominator. $\endgroup$ – Jorge Fernández Hidalgo Jun 9 '14 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.