# combinatorics – Maximization problems related to graph coloring

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.$$