It's well-known that chromatic polynomials count colorings which differ by permutations of colors. What is known about their analogues which don't count such colorings as distinct?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Up to isomorphism there is a finite number of colorings, so no polynomial (or unbounded) counting function exists if you allow arbitrary relabeling of the colors.
Probably you meant permutation of the actually utilized colors within each coloring. But here the interpretation of "permutation" is not unique. There are permutations of the $k$ utilized colors (there is some $G$-dependent linear transform for this, similar to replacing ordinary generating functions by exponential generating functions), permutations of the $k$ utilized colors that are induced by automorphisms of the graph, and maybe some weighting of the first type of permutations using the action of automorphisms (as in Wick's formula). Also, without thinking about this carefully, it might be necessary to distinguish between automorphisms of the graph and automorphisms of the graph partition determined by the coloring.
So I guess you either want a version of the chromatic polynomial accounting for automorphisms, or some transformed polynomial that contains the same information as the chromatic polynomial.