1
$\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 in Mathematica to list all proper $k$-colorings of the vertices?

The chromatic polynomial can count them easily.

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 Combinatorica function MinimumVertexColoring[g,6,All], with g the ladder rung graph $6P_2$.

See also the cross-post Coloring ladder rung graphs.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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