co.combinatorics - 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