Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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