3 added 271 characters in body

In general this is hard, unless you have a specific graph structure in mind. To find the number of $k$-colorings of your graph $G$ is equivalent to calculating it's chromatic polynomial and this is NP-hard. When you have $r$ unstable vertices, this is equivalent to finding a subgraph of $H$ your graph $G$ of size $r$ with no isolated vertices and then finding the number of $k$-colorings of $G/\sim$, where we identified points belonging to the same connected component in $H$. I don't see a reason to expect a tractable answer in general.

Since you are interested in cyclic graphs, let the chromatic polynomial of the cyclic graph on $n$ vertices be $\pi_n(x)$. Let $g_n(k,m)$ be the number of $m$ colorings where there are $k$ unstable vertices. Then we have $$g_n(0,m)=\pi_n(m)=(m-1)^n+(-1)^n(m-1).$$ Clearly you have $g_n(1,m)=0$ and to calculate $g_n(k,m)$ let us denote by $p(k,r)$ the number of cyclical partitions of $n$ into $r$ parts of size at $\geq 2$ and $n-k$ singletons (this has a closed formula that isn't very hard to derive). Now we have $$g_n(k,m)=\sum_{r\geq 1}p(k,r)g_{n-k+r}(0,m)$$ by the obvious correspondence where each block of the partition is monochromatic. On a different note, you might find the paper "A new two-variable generalization of the chromatic polynomial" by K. Dohmen, A. Ponitz and P. Tittmann interesting. It talks about a similar but not same way of considering colorings with "proper" and "non-proper" vertices.

2 added 654 characters in body

In general this is hard, unless you have a specific graph structure in mind. To find the number of $k$-colorings of your graph $G$ is equivalent to calculating it's chromatic polynomial and this is NP-completeNP-hard. When you have $r$ unstable vertices, this is equivalent to finding a subgraph of $H$ your graph $G$ of size $r$ with no isolated vertices and then finding the number of $k$-colorings of $G/\sim$, where we identified points belonging to the same connected component in $H$. I don't see a reason to expect a tractable answer in general.

Since you are interested in cyclic graphs, let the chromatic polynomial of the cyclic graph on $n$ vertices be $\pi_n(x)$. Let $g_n(k,m)$ be the number of $m$ colorings where there are $k$ unstable vertices. Then we have $$g_n(0,m)=\pi_n(m)=(m-1)^n+(-1)^n(m-1).$$ Clearly you have $g_n(1,m)=0$ and to calculate $g_n(k,m)$ let us denote by $p(k,r)$ the number of cyclical partitions of $n$ into $r$ parts of size at $\geq 2$ and $n-k$ singletons (this has a closed formula that isn't very hard to derive). Now we have $$g_n(k,m)=\sum_{r\geq 1}p(k,r)g_{n-k+r}(0,m)$$ by the obvious correspondence where each block of the partition is monochromatic.

1

In general this is hard, unless you have a specific graph structure in mind. To find the number of $k$-colorings of your graph $G$ is equivalent to calculating it's chromatic polynomial and this is NP-complete. When you have $r$ unstable vertices, this is equivalent to finding a subgraph of $H$ your graph $G$ of size $r$ with no isolated vertices and then finding the number of $k$-colorings of $G/\sim$, where we identified points belonging to the same connected component in $H$. I don't see a reason to expect a tractable answer in general.