Tractably Partitioning the possible vertex k-colorings of a graph by local stability and instability. - MathOverflow

Tractably Partitioning the possible vertex k-colorings of a graph by local stability and instability.

2010-08-17T23:38:06Z

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

Answer by Gjergji Zaimi for Tractably Partitioning the possible vertex k-colorings of a graph by local stability and instability.

2010-08-18T00:06:52Z

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.

Answer by Apurva for Tractably Partitioning the possible vertex k-colorings of a graph by local stability and instability.

2010-08-19T19:14:47Z

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