$G$ and $f(S)$ be the sum of labels over a set $S \subset V$, $f(S) = \sum_{u \in S} f(u)$. A labeling $f$ is a *$k$-coloring* if $f(u) \neq f(v)$ for all edges $(u,v) \in E$. Also, a labeling is an *additive $k$-coloring* if $f(N(u)) \neq f(N(v))$ for all edges $(u,v) \in E$. The *chromatic number* (resp. *additive chromatic number*) of $G$ is defined as the least number $k$ for which $G$ has a $k$-coloring (resp. additive $k$-coloring) $f$, and is denoted by $\chi(G)$ (resp. $\eta(G)$). The Graph Coloring Problem (GCP) and Additive Coloring Problem (ACP) consist of finding such numbers and both are -hard problems (see [@LUCKYCOMPLEXITY] for the last one).

GCP and ACP share some immediate properties. In both problems one can be restricted to work with connected graphs since the (additive) chromatic number of a graph with several connected components is the maximum of the (additive) chromatic numbers of those components. Also, if a graph has a (additive) $k$-coloring it also has (additive) $(k+1)$-coloring. In addition, (additive) 1-colorings are easily characterizable:

\[ADDITIVE1\] For a given graph $G = (V, E)$, $\eta(G) = 1$ if and only if $d(u) \neq d(v)$ for all $(u,v) \in E$.

On the 