Minimum number of links connecting two nodes of the same color

Question

Preliminaries

Consider an undirected network of $N$ nodes ($V$ is the set of nodes), described by the symmetric adjacency matrix $A = \{a_{v,w}\} \in \{0,1\}^{N \times N}$ without self-loops (i.e. $a_{v,w} = 1$ if $v$ and $w$ are connected, and $0$ otherwise; moreover, $a_{v,v} = 0 ~\forall v \in V$). Suppose that for each node, there exists a path towards any other node (the graph is connected).

Now, consider a coloring $\alpha \in K^N$, where $K$ is the set of colors ($|K| \geq 2$), such that for any node $v$ there exists another node $w$ connected to $v$ (i.e. $a_{v,w}=1$ ) with the same color of $v$ (i.e. $\alpha_w = \alpha_v$).

Let's introduce the set

$$B(\alpha) = \left\{\beta \in K^N : \beta_v \neq \alpha_v ~\forall \in V\right\}.$$

In other words, $B(\alpha)$ contains all the colorings such that all nodes have different color with respect to $\alpha$.

The problem

I'm looking for the solutions of this maximization problem:

$$M(\alpha) = \max_{\beta \in B(\alpha)} \sum_{v\in V}\left(\sum_{\substack{w \in V \\ \alpha_w = \alpha_v}}a_{v,w} - \sum_{\substack{w \in V \\ \beta_w = \beta_v}}a_{v,w}\right).$$

My question

This problem can be numerically solved by rewriting it in a integer-programming fashion. Anyway, I'd like to know if this problem has been already studied, and there are some results on the value of $M(\alpha)$ (i.e. upper and lower bounds). Numerically (i.e. by checking this value for several randomly generated networks), it seems that:

$$M(\alpha) \leq N.$$

Alternative version of the problem

As it has been highlighted by Misha Lavrov, the problem can be stated as follows:

Find

$$m(\alpha) = \min_{\beta \in B(\alpha)} \sum_{v\in V}\sum_{\substack{w \in V \\ \beta_w = \beta_v}}a_{v,w},$$

i.e. find the coloring $\beta$ such that it guarantees the minimum number of connections among nodes of the same colors. My claim is that:

$$m(\alpha) \geq \sum_{v\in V}\sum_{\substack{w \in V \\ \alpha_w = \alpha_v}}a_{v,w} - N,$$

since

$$M(\alpha) = \sum_{v\in V}\sum_{\substack{w \in V \\ \alpha_w = \alpha_v}}a_{v,w} - m(\alpha).$$

Answer 1

I think that the bound is not working, For example taking the following adjency matrix, the fixed coloring (with $K=\{0,1,2\}$): \begin{align} A = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}, \quad \alpha = \begin{pmatrix} 0\\ 0\\ 0\\ 1\\ 1\\ 2\\ 2 \end{pmatrix}, \quad \beta = \begin{pmatrix} 1\\ 1\\ 2\\ 0\\ 2\\ 1\\ 0 \end{pmatrix} \end{align}

As you can see $f(\alpha) = 10$ and $f(\beta) = 2 < 10 - 7 = f(\alpha) - N$.

Answer 2

Let $k = |K|$, and $f(\chi)$ be the number of edges whose two endpoints have the same color in coloring $\chi$.

If $k = 2$, the gap is always $0$, i.e., $f(\alpha)$ is always equal to $f(\beta)$.

If $k > 2$, the gap can in fact be as high as $\Theta(N^2/k^2 - k)$. In fact, let the graph consist of $k$ (almost) equal-sized bipartite graphs (with $k$ more edges to make it connected). Here each bipartite has (almost) equal number of nodes on each side and full connection in-between. Let $\alpha$ color each bipartite graph a different color. We have $f(\alpha) = \Theta(N^2/k^2)$. We can in fact choose $\beta$ such that $f(\beta) = O(k)$ (here we use the property that $k > 2$). Hence the gap.