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



Tractably Partitioning the possible vertex k-colorings of a graph by local stability and instability.
If you limit it to specific classes of graphs, say for example star graphs, you can come up with some answers. For a star graph $S\_m$, with a vertex at the center and $m$ vertices connected to the center, yielding a graph $G$ with $n=m+1$ vertices and $m$ edges, it can be calculated that for $k=2$


If the center vertex is labeled black, then the only "0-unstable" coloring is where all of the leaves are white. If any of the leaves are also black, say $j$ of the $m$ leaves are black while the center is also black, then the center and those $j$ black leaves are unstable, leaving $m-j$ leaves as stable nodes. There are $m \choose j$ = ($m$ choose $j$) ways to color $j$ of the $m$ leaves as black.


The same is true with the color labels reversed if the center is labeled white.
Thus for $k=2$, for two-color labeling of a star-graph $S\_m$ with $m$ leaves and $n=m+1$ vertices, the sizes of the partitions of all of the possible two-colorings are as follows:


|{0 unstable}| = 2 


|{1 unstable}| = 0 


|{r unstable}| = $2 \times$ ${m}\choose{r-1}$ for $ 2 \le r \le n$, with $r \in Z $


The size of the 1-unstable partition is always zero for this family of graphs. The size of the 1-unstable partition is always zero for any graph and for any $k$ because instablity occurs over an edge linking two vertices with the same color label, thus always creating two unstable vertices if there are any unstable vertices at all.


The sum of all of these partitions sizes is $2^n$, thus all of the possible $2^n$ colorings of the $n=m+1$ vertex star graph $S\_m$ have been accounted for. A similar calculation can be made for star graphs for $k>2$.


Apurva


