Words and profiles

Definition

Let $G$ be a finite graph with chromatic number $\chi(G)$. Let $\mathcal C$ be a set of colors with $|\mathcal C|=\chi(G)$.

Words and profiles are defined as follows.

A word on $G$ is any map $w:V(G)\to\mathcal C$. The word need not be a proper colouring: adjacent vertices may get the same color.

The profile of a word $w$ is the vector $\mathbf m(w)=(m_X(w))_{X\in\mathcal C}$. Its entry $m_X(w)=|w^{-1}(X)|$ is the number of vertices of color $X$.

Vectors are written in bold, and inequalities between vectors hold in every coordinate. The vector $\mathbf e_X$ has entry $1$ at $X$ and $0$ elsewhere. The vector $\mathbf 1$ has every entry equal to $1$.

Let $\mathcal P(G)$ be the set of proper colorings of $G$ with palette $\mathcal C$. Since $|\mathcal C|=\chi(G)$, each coloring in $\mathcal P(G)$ uses every color.

A profile $\mathbf m$ is feasible if $\mathbf m=\mathbf m(w)$ for some $w\in\mathcal P(G)$.