0
$\begingroup$

I can use various algorithms to list all proper $k$-colorings of the vertices of the ladder rung graph $nP_2$, the first six are show below.

enter image description here

Is there a quick way to list all proper $k$-colorings of the vertices?

The chromatic polynomial can count them easily (i.e. is quick to compute).

But does the nature of the graph present a coloring technique which improves the brute force method of checking every possible coloring for at least one pair of similar, adjacent colors, rejecting, and then keeping the rest?

So far, even for $n=6$, listing all $6$-colorings takes weeks of computational time using the best known graph coloring algorithms in Mathematica 12.

$\endgroup$
3
  • $\begingroup$ Sorry, so coloring this is like assigning a color to each vertex in the top and assigning other coloring to the bottom, so there are $k^n(k-1)^n$ of them, no? What do you mean by generated them? you want to represent them as a bijection of possible functions from $[n]$ to $[k(k-1)]$? how do you want your colorings? $\endgroup$
    – Phicar
    Sep 4, 2019 at 21:09
  • $\begingroup$ To list them all with an algorithm. They are easy to count. $\endgroup$
    – apg
    Sep 4, 2019 at 21:11
  • $\begingroup$ Yes, but listing all of them like having all of them? That is a lot of memory to handle. Having one at a time is good enough for you? $\endgroup$
    – Phicar
    Sep 4, 2019 at 22:49

1 Answer 1

Reset to default
1
$\begingroup$

The function FindProperColorings in the Wolfram Function Repository generates all proper k-colorings of a graph.

https://resources.wolframcloud.com/FunctionRepository/resources/FindProperColorings

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .