**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 Vright}.$$

In other words, $B(alpha)$ contains all the colorings such

that all players have different color with respect to $alpha$.

**The problem**

I’m looking for the solutions of thess maximization problems:

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

$$M_2(alpha) = max_{beta in B(alpha)} sum_{vin 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**

These problems can be numerically solved by rewriting them in a integer-programming fashion. Anyway, I’d like to know if these problems have been already studied, and there are some results on the value of $M_1(alpha)$ and $M_2(alpha)$ (i.e. upper and lower bounds).

Numerically (i.e. by checking this value for several randomly generated networks), it seems that:

$$M_1(alpha) leq N ~text{and}~ M_2(alpha) leq N.$$