A k-coloring or k-labeling of the vertices of a single-component undirected graph G with $n$ vertices can be a proper coloring or not. If it is not a proper coloring, such that each vertex has neighbors on its edges which are of a different color or label, then for each possible labeling, it possible to count the number of vertices which have a proper coloring locally as an integer $x \in \{0,n\}$, and those which do not $y = n-x$. Let us call the vertices which are locally properly colored "stable", and those which have at least one neighbor with the same color label "unstable." The set of all possible labelings, of which there are $k^n$ can be partitioned into $n+1$ sets by the metric of how many vertices are unstable for each coloring.

What is the size of each partition from 0-unstable to n-unstable? *Is there a particular name for this type of partitioning?* Obviously, if we are setting $k=2$, then the size of the partition of 0-unstable is 2 if the graph G is bipartite and allows for a proper-2-coloring; if $k=3$ and the graph is 3-colorable, then the size of the partition of 0-unstable is 6; etc.

Of course, this partitioning can be calculated by brute force methods in exponential time ($k^n$) by enumerating over all possible labelings with $k$ labels on a graph with $n$ vertices.

For what classes of graphs is the problem tractable? For example, as described below in one answer, for star graphs $S_m$ with $m$ leaves and $n=m+1$ vertices, the distribution is almost the binomial distribution, with $2$ as the size of the 0-unstable partition, zero as the size of the 1-unstable partition, and $2 {m \choose j-1}$ as the size of the $j$-unstable partition where $1\lt j \le n$.

ABmd