I am a layman when it comes to mathematics, computer science and , thus, also graph theory.
But for designing a psychological experiment based on simple graphs I need to know how to find the number of vertex colorings of a given graph.
What I found out so far is that the total number of possible vertex colorings depending on the number of colors used is given in the Chromatic Polynomials belonging to the same graph. However, this total number of possible colorings is very high since it contains all the structurally equal colorings with only the colors simply swapped. And I am actually interested in the much lower number of structurally distinct colorings.
I know that this question is very similar to this post on mathoverflow. But I think mine is a bit more specific down below and, hence, slighlty differs from that one.
I will also use the image from that post to illustrate the problem:
As you can see the graph depicted has overall 12 possible colorings, which you can calculate from the chromatic polynomials. However, only two of these differ from each other structurally, i.e. apart from mere swapping of colors.
So what I learned from that post mentioned above is, that you should get the number of truly distinct colorings by calculating the chromatic polynomials for the desired number of colors x and divide the result by the factorial of x (x!). I now use the tool from this website to calculate the chromatic polynomials for a graph with its chromatic number (which is what I'm interested in) as x and divide by x!. For the example in the image this yields (3^4 - 4 * 3^3 + 5 * 3^2 - 2 * 3^1) / 3! = 12 / 6 = 2. So far so good.
I went through another example, which is the following graph:
This is an isomorph of G149 from "An Atlas of Graphs" in hexagon shape. Its chromatic number is 3. I get the chromatic polynomials x^6 - 8 * x^5 + 27 * x^4 - 47 * x^3 + 41 * x^2 - 14 * x^1 from this online tool again. Calculating it with 3 for x and dividing the result by 3! gives me 5 as a result.
Now I wanted to draw those five different colorings as a visual demonstration of the result. But to my surprise I managed to only do 3 colorings that differ from eachother structurally and not just in swapping of colors. Here they are:
Am I just missing something? Or what is the problem here? Why do I end up with 5 by calculating and with 3 by drawing? And: How can I reliably and easily find the number of truly distinct colorings of a given graph (I'm currently only interested in undirected planar graphs with up to 7 vertices and up to 12 edges)?
Some elucidating help would be highly appreciated!
UPDATE: I have to apologise. I just tried again to find the 5 colorings of the graph in example 2 manually ... and apparently my thinking had got stuck into some kind of impasse state. Anyway, I now found the missing two colorings:
So chromatic polynomials divided by x! (with x = number of colors) seems to work reliably.
However, I would still love to hear whether anyone knows an easier and quicker way of getting the number that I'm interested in. Is there maybe also a tool, that draws those "truly distinct" colorings for a given graph?