The standard definition of graph coloring (see here) on undirected graphs is:

A coloring is a labeling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color.

It is well-known that the chromatic number of a graph $G$, $\chi(G)$, denotes the minimum number of colors required in order to have a "proper" graph coloring.

Now, suppose that the number of available colors is $k < \chi(G)$. In this case, any assignment of colors to the vertices can be seen as a weak graph coloring, since there are for sure at least two connected vertices sharing the same color.

In this contest, given an undirected graph $G$ of $N$ nodes represented by a binary adjacency matrix $A$, and a weak graph coloring $\alpha \in \{1, \ldots, k\}^N$ (i.e. a generic assignment of colors to the vertices of $G$), one can define a loss function as:

$$\mathcal{L}(G, \alpha) = \frac{1}{2}\sum_{v = 1}^N \sum_{w = 1}^N a_{v,w} \delta_{\alpha_v, \alpha_w},$$

where $\alpha_v$ is the color of node $v$, $\alpha_w$ is the color of $w$ and $\delta_{x,y}$ is the Kronecker delta (i.e. $\delta_{x,y} = 1 \iff x=y$, and $\delta_{x,y}=0 \iff x \neq y$). The function $\mathcal{L}(G, \alpha)$ counts the number of links connecting nodes with the same color.

Of course, when $\alpha$ is a "proper" coloring (i.e. $\chi(G) = k$), $\mathcal{L}(G, \alpha) = 0$, while in the "weak" case, $\mathcal{L}(G, \alpha) > 0$.

Is there any literature/references on this kind of problems, on this loss function and on its optimization? Thanks in advance!

  • $\begingroup$ @MorganRodgers thanks for this comment. I've searched around for "defective colorings" and it is quite close to what I'm looking for. $\endgroup$ Commented Oct 1, 2021 at 17:31

1 Answer 1


Check out the Maximum Satisfiability Problem or MAX-SAT https://en.wikipedia.org/wiki/Maximum_satisfiability_problem


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .