# Graph coloring with an efficient running time

Let $$G(V,E), |V| = n,$$ be a (undirected) graph and a coloring function $$f: V\rightarrow \{1,2,3...s \}$$ which assigns to each vertex a color, such that in total there are $$n/s$$ vertices of each of the $$s$$ colors.

Starting from a given vertex $$a$$, the task is to find out if there is a path in the graph, such that it contains all the s colors which are nevertheless represented only once in the path. I guess one way to handle this is to assign to each vertex a list or eventually a dictionary of all colors it is connected to but it's own color. In that case one would have to consider each vertex starting from $$a$$ such that in it's list of colors it contains at least one color. But as far as I can see it will lead to a brute force algorithm.

Can one do better than this ? Thanks for any help.

The problem is NP-hard: it is as hard as Hamiltonian path, when $$s=n$$ and $$f$$ is a bijection. Therefore, you shouldn't expect any efficient algorithm that always works. You could study algorithms for the Hamiltonian path problem and try generalizing them to your situation (e.g., using a SAT solver).
• Thanks. One might use dynamic programming (Bellman-Held-Karp) in the case of the Hamiltonian path problem that aims at finding a path through all the vertices which is different from the problem above in that we need to consider a subset $S \subset V, |S| = s$ satisfying the required property. You are suggesting to adapt this to the problem above by using a SAT solver. I do not have any experience with the SAT solver. Sep 6, 2022 at 9:36