# Graph coloring when available colors are less than chromatic number

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!

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