Words and profiles

Summary

A word on a graph $G$ is any map $w:V(G)\to\mathcal C$ into a set of colors, proper or not. Its profile is the vector $\mathbf m(w)$ whose entry $m_X(w)=|w^{-1}(X)|$ counts the vertices that get color $X$.

Take $|\mathcal C|=\chi(G)$, the chromatic number of $G$. Then each proper colouring with palette $\mathcal C$ uses every color, and a profile is feasible if some such coloring has it.