---
abstract: |
    Let $f:V \rightarrow \{1,\ldots,k\}$ be a labeling of the vertices of a graph $G = (V,E)$ and denote with $f(N(v))$ the sum of the labels of all vertices adjacent to $v$. The least value $k$ for which a graph $G$ admits a labeling satisfying $f(N(u)) \neq f(N(v))$ for all $(u,v) \in E$ is called *additive chromatic number* of $G$ and denoted $\eta(G)$. It was first presented by Czerwiński, Grytczuk and Zelazny who also proposed a conjecture that for every graph $G$, $\eta(G) \leq \chi(G)$, where $\chi(G)$ is the chromatic number of $G$. Bounds of $\eta(G)$ are known for very few families of graphs. In this work, we show that the conjecture holds for split graphs by giving an upper bound of the additive chromatic number and we present exact formulas for computing $\eta(G)$ when $G$ is a fan, windmill, circuit, wheel, complete split, headless spider, cycle/wheel/complete sun, regular bipartite or complete multipartite observing that the conjecture is satisfied in all cases. In addition, we propose an integer programming formulation which is used for checking the conjecture over all connected graphs up to 10 vertices.

    additive chromatic number $\cdot$ additive coloring conjecture $\cdot$ lucky labeling
author:
- 'D. Severín'
title: On the additive chromatic number of several families of graphs
---

Introduction
============

Several combinatorial optimization problems concern finding means to distinguish the vertices of a graph. Such identification can be *global*, when each vertex is uniquely identified from the solution of the optimization problem, or *local*, when for every edge $(u,v)$, $u$ and $v$ can be distinguished each other from the solution of the optimization problem. Usually the solution restricted to the closed neighborhood of a vertex is used for that identification, although open neighborhood can be used as well. Most of these problems are coloring problems. On the side of global identification problems we can mention *Identification Code Problem* [@KARPOVSKY] and *Recognizable Coloring of Graphs* [@RECOGNIZABLE]. On the side of local ones, *Locally Identifying Coloring of Graphs* [@ESPERET] and several problems where open neighborhood is used for identification: *Vertex Coloring by Sums*, *Products* and *Multisets* among others [@SEAMONE].

In this paper we address one of these problems, specifically the Vertex Coloring by Sums, which is also called *Additive Coloring Problem* or *Lucky Labeling Problem*. It was first presented by Czerwiński, Grytczuk and Zelazny [@LUCKYORIGINAL] who proposed a conjecture that for every graph $G$, $\eta(G) \leq \chi(G)$, where $\chi(G)$ is the chromatic number of $G$ and $\eta(G)$ is the additive coloring number of $G$, defined below. The problem as well as the conjecture has recently gained interest from the scientific community [@LUCKYCOTAINF; @ORLOW; @LUCIANO; @LUCKYCOMPLEXITY; @LUCKYCOTASUP; @ADDITIVEPLANAR; @LUCKYCHOICE; @DLUCKY]. However, the additive chromatic number is known for very few families of graphs.

Below, we make some basic definitions to formalize these concepts. For a given integer $k$, denote the set $\{1,2,\ldots,k\}$ with $[k]$. Let $G = (V, E)$ be a finite, undirected and simple graph. Usually, $V = [n]$ where $n$ is the number of vertices of $G$. For each $v \in V$, let $N_G(v)$ be the set of neighbors of $v$ and $d_G(v)$ its degree, $d_G(v) = |N_G(v)|$. Also, $N_G[v] = N_G(v) \cup \{v\}$. Let $D = (V, A)$ be a finite directed graph. For each $v \in V$, define $N_D^-(v) = \{(u,v) \in A : u \in V\}$, $N_D^+(v) = \{(v,w) \in A : w \in V\}$ and $N_D(v) = N_D^-(v) \cup N_D^+(v)$. When the graph or digraph is inferred from the context, we omit the subindex, $d(v), N(v), N[v], N^-(v), N^+(v)$.

Let $f : V \rightarrow [k]$ be a labeling of the vertices of $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 other hand, if $G'$ is a subgraph of $G$, we have $\chi(G') \leq \chi(G)$ but the same property does not hold for ACP. For instance, $\eta(P_2) = 2$ but $\eta(P_3) = 1$. And, for graphs $G$ with maximum degree $\Delta$, the best known upper bound of $\eta(G)$ is $\Delta^2 - \Delta + 1$ [@LUCKYCOTASUP], as opposed to Brooks’ result for GCP ($\chi(G) \leq \Delta+1$) which is significantly better.

Constant upper bounds of the additive chromatic number are known for some families of graphs: if $G$ is a tree, $\eta(G) \leq 2$; if $G$ is planar bipartite, $\eta(G) \leq 3$ [@LUCKYORIGINAL]; if $G$ is planar, $\eta(G) \leq 468$ [@ADDITIVEPLANAR] and if $G$ is planar of girth at least 26, $\eta(G) \leq 3$ [@LUCKYCHOICE]. Other upper bounds can be consulted in [@LUCKYORIGINAL; @ADDITIVEPLANAR; @LUCKYCHOICE].

Regarding lower bounds of $\eta(G)$, one of them can be computed as follows. If $G$ has *true twins* vertices $u$ and $v$ ($N[u] = N[v]$), then an additive coloring $f$ of $G$ must satisfy $f(u) \neq f(v)$. Therefore:

\[LOWERBOUNDTWINS\] Let $T \subset V$ such that any $u,v \in T$ are true twins of $G$. Then, $\eta(G) \geq |T|$.

The given formula can be applied to prove that $\eta(K_n) = n$ [@LUCKYORIGINAL].\
When a graph has an additive coloring, an acyclic orientation of this graph arises. In fact, one can obtain the additive chromatic number of a graph by exploring their acyclic orientations and solving, for each one, a problem called *Topological Additive Numbering* (TAN) [@IPL2013]. We introduce more definitions in order to explain this approach. Let $D = (V, A)$ be a directed acyclic graph and $G(D)$ be the undirected underlying graph of $D$. We say that $D$ *represents an acyclic orientation* of $G$ if $G(D)$ is isomorphic to $G$. Let $f: V \rightarrow [k]$ be a labeling of vertices of $D$. If $f(N(u)) < f(N(v))$ for every $(u, v) \in A$, then $f$ is called *topological additive $k$-numbering* of $D$. The *topological additive number* of $D$, denoted by $\eta_t(D)$, is defined as the least number $k$ for which $D$ has a topological additive $k$-numbering, or $+\infty$ in case that such $k$ does not exist (knowing this parameter is -hard [@IPL2013]). Now, the following relationship becomes apparent: $$\eta(G) = \min \{ \eta_t(D) ~:~ D~\textrm{represents an acyclic orientation of}~G \}$$ We can take advantage of properties known for TAN. For instance, the following result provides a lower bound of $\eta_t(D)$ and, therefore, $\eta(G)$:

[@IPL2013] Let $D = (V,A)$ be a directed acyclic graph such that its vertices are ordered so that $(u, v) \in A$ implies $u < v$. If $Q$ is a clique of $G(D)$ and $q_F$, $q_L$ are the smallest and largest vertices of $Q$ respectively, then $$\eta_t(D) \geq \biggl\lceil \dfrac{d(q_F)+1}{d(q_L)-|Q|+2} \biggr\rceil.$$

\[COTAINF\] Let $G$ be a graph and $Q$ be a clique of $G$. If $d_1$, $d_2$ are the degrees of the vertices of $Q$ with smallest and largest degree respectively, then $$\eta(G) \geq \biggl\lceil \dfrac{d_1+1}{d_2-|Q|+2} \biggr\rceil.$$

The latter bound can be relaxed by considering $d_1 \geq |Q|-1$ and $d_2 \leq n-1$. Hence, $\eta(G) \geq \lceil \frac{|Q|}{n-|Q|+1} \rceil$, which is a lower bound previously proposed in [@LUCKYCOTAINF].\
As we mentioned before, one of the reasons to study ACP is that this problem and GCP seem to be related as follows:

**Additive Coloring Conjecture.** [@LUCKYORIGINAL] For every graph $G$, $\eta(G) \leq \chi(G)$.

It is known that the conjecture holds for trees [@LUCKYORIGINAL; @ORLOW] and, recently, for non-bipartite planar graphs of girth at least 26 [@LUCKYCHOICE]. Our contribution in this work is to give the exact value of the additive chromatic number of several families of graphs and expand the number of cases in which the conjecture is satisfied. In addition, we propose an integer programming formulation for ACP which is used for checking the conjecture over all connected graphs up to 10 vertices.

Regular bipartite and complete multipartite graphs
==================================================

As far as we know, the conjecture has not been proved for bipartite graphs yet. We show that the conjecture holds for a subclass of bipartite graphs including regular ones, when its vertices have the same degree.

Let $G = (U \cup V, E)$ be a bipartite graph ($U$ and $V$ are its stable sets) such that, for all $v \in V$ and $u \in N(v)$, $d(u) < 2 d(v)$. If $d(u) \neq d(v)$ for all $(u,v) \in E$ then $\eta(G) = 1$, otherwise $\eta(G) = 2$.

In virtue of Observation \[ADDITIVE1\], we only have to prove $\eta(G) \leq 2$. Consider the assignment $f:V \rightarrow \{1,2\}$ such that $f(u) = 2$ for all $u \in U$ and $f(v) = 1$ for all $v \in V$. Then, $f(N(u)) = d(u) < 2 d(v) = f(N(v))$ for all $(u,v) \in E$.

\[REGULARBIP\] If $G$ is a regular bipartite graph, then $\eta(G) = 2$.

Now, we consider complete multipartite graphs. We say that a digraph $D$ is *complete $r$-partite* when $G(D)$ is complete $r$-partite. We say that $D$ is *monotone* when $V(D)$ can be partitioned into subsets $V_1, V_2, \ldots, V_r$ such that every arc in $V_i \times V_j$ satisfies $i < j$. We cite a result given in [@IPL2013] as a lemma:

[@IPL2013] \[LEMITA\] Let $D$ be a complete $r$-partite digraph. Then, $\eta_t(D) < +\infty$ if and only $D$ is monotone. In that case, $$\eta_t(D) = \max \biggl\{ \biggl\lceil \dfrac{s_i}{|V_i|} \biggr\rceil : i \in [r] \biggr\},$$ where $V_1, \ldots, V_r$ is the partition of $V(D)$, $s_r = |V_r|$ and $s_i = \max\{1 + s_{i+1}, |V_i|\}$ for all $i \in [r-1]$.

Let $G=(V_1 \cup \cdots \cup V_r,E)$ be the complete $r$-partite graph ($V_1$,$\ldots$, $V_r$ are its stable sets) and $|V_i| \geq |V_{i+1}|$ for all $i \in [r-1]$. Then, $\eta(G) = \max \{ \lceil \frac{s_i}{|V_i|} \rceil : i \in [r] \}$ where $s_r = |V_r|$ and $s_i = \max\{1 + s_{i+1}, |V_i|\}$ for all $i \in [r-1]$. Moreover, $\eta(G) \leq r$.

Let $D$ be the monotone digraph such that $G(D) = G$ and the partition of $V(D)$ is $V_1, V_2, \ldots, V_r$. We must prove that $D$ represents the acyclic orientation of $G$ that provides the lowest value of $\eta_t(D)$. Let $D'$ be another digraph representing an acyclic orientation of $G$ with $\eta_t(D') < \infty$. Therefore, $D'$ is a monotone complete $r$-partite digraph where $G(D')$ is isomorphic to $G$ and the partition of $V(D')$ is $V'_i = V_{\mathfrak{p}(i)}$ for all $i \in [r]$ where $\mathfrak{p}:[r] \rightarrow [r]$ is some permutation function. Define $s_i$ and $s'_i$ for $D$ and $D'$ respectively as in Lemma \[LEMITA\]. It is easy to verify that sequences $\{s_i\}_{i \in [r]}$ and $\{s'_i\}_{i \in [r]}$ are decreasing, and $s'_i \geq s_i$ for all $i \in [r]$. Let $i$ be an integer such that $s_i/|V_i|$ is maximum and $I = \{ t \in [r] : |V_t| = |V_i|\}$. Note that $i$ is the minimum index of $I$. Let $J = \{ t \in [r] : |V'_t| = |V_i|\}$ and $j$ be the minimum index of $J$. Due to the ordering in the cardinality of sets of $V(D)$, $i \geq j$. Hence, $s'_j \geq s'_i \geq s_i$. Since $j \in J$, $|V'_j| = |V_i|$ and we obtain $s'_j/|V'_j| \geq s_i/|V_i|$. Therefore, $\eta_t(D') \geq \lceil s'_j/|V'_j| \rceil \geq \lceil s_i/|V_i| \rceil = \eta_t(D)$.

Now, we show that $\eta(G) \leq r$. We first prove by induction on $i$ that $s_i \leq |V_i|(r - i + 1)$ for $i = r, r-1, \ldots, 1$. In first place, if $i = r$, clearly $s_r = |V_r| = |V_r|(r - r + 1)$. If $i < r$, just two cases are possible. If $s_i = |V_i|$, clearly $s_i \leq |V_i|(r - i + 1)$. Otherwise, $s_i = 1 + s_{i+1}$. By the inductive hypothesis $s_{i+1} \leq |V_{i+1}|(r - i)$ and the fact that $|V_i| \geq |V_{i+1}|$, we obtain: $$s_i = 1 + s_{i+1} \leq 1 + |V_{i+1}|(r - i) \leq |V_{i+1}|(r - i + 1) \leq |V_i|(r - i + 1).$$ Hence, $\bigl\lceil \frac{s_i}{|V_i|} \bigr\rceil \leq r - i + 1 \leq r$ for all $i$ and therefore $\eta(G) \leq r$.

Since $\chi(G) \geq r$ for any complete $r$-partite graph $G$, we conclude that the conjecture holds for these graphs.

Join with complete graphs
=========================

Let $G_1, G_2$ be disjoint graphs. The *join* of $G_1$ with $G_2$, denoted $G_1 \lor G_2$, is defined as the resulting graph $G'$ satisfying $V(G') = V(G_1) \cup V(G_2)$ and $E(G') = E(G_1) \cup E(G_2) \cup \{ (u,v) : u \in V(G_1),~ v \in V(G_2)\}$. Given a graph $G$, the following result allows to solve the ACP of a join of $G$ with a complete graph by just solving the ACP of $G$:

\[UNIVERTICES\] Let $G$ be a graph of $n$ vertices and $\Delta$ be the largest degree in $G$. Then, $\eta(G \lor K_q) = \max \{ \eta(G), q \}$ for all $q \leq n-\Delta-1$.

Let $V$ and $E$ be the set of vertices and edges of $G$ respectively, $U = \{ u_1, u_2, \ldots, u_q \}$ be the set of vertices of $K_q$, $G' = G \lor K_q$ and $f$ be an optimal additive coloring of $G$. Consider a labeling $f'$ of $G'$ satisfying $f'(v) = f(v)$ for all $v \in V$, and $f'(u_i) = i$ for all $i \in [q]$. Now, for any $(v,v') \in E$, $f'(N_{G'}(v)) = f(N_G(v)) + f'(U) \neq f(N_G(v')) + f'(U) = f'(N_{G'}(v'))$. For any $i,j \in [q]$ such that $i < j$, $f'(N_{G'}(u_i)) = f(U \cup V) - i > f(U \cup V) - j = f'(N_{G'}(u_j))$. Finally, note that $f'(V \backslash N_G(v)) \geq n - d_G(v) \geq n - \Delta$ for all $v \in V$. Then, for any $u \in U$ and $v \in V$, $f'(N_{G'}(u)) = f'(U \cup V) - f'(u) \geq f'(U \cup V) - q > f(U \cup V) - n + \Delta \geq f'(U \cup V) - f'(V \backslash N_G(v)) =
f'(N_{G'}(v))$. Therefore, $f'$ is an additive coloring of $G'$.

In order to prove optimality, note first that any two vertices in $U$ are true twins of $G'$. By Observation \[LOWERBOUNDTWINS\], $\eta(G') \geq q$. In addition, suppose that $\eta(G') < \eta(G)$. Hence, there exists an additive $k$-coloring $f'$ of $G'$ with $k = \eta(G)-1$. Let $f$ be the labeling of $G$ satisfying $f(v) = f'(v)$ for all $v \in V$. We have $f(N_G(v)) = f'(N_{G'}(v)) - f'(U) \neq f'(N_{G'}(v')) - f'(U) = f(N_G(v'))$ for any $(v,v') \in E$. Therefore, $f$ is an additive $k$-coloring of $G$ which leads to a contradiction.

When Theorem \[UNIVERTICES\] is applied one must keep in mind that the size of a complete graph that can be joined to a graph is limited by $n-\Delta-1$. In fact, if one chooses $q = n-\Delta$, $\eta(G \lor K_q) = \max \{ \eta(G), q \}$ does no longer hold. For instance, let $G$ be the graph of Figure \[CONTRAEJEMPLO\] and $q = 2$. It can be proven that $\eta(G)=2$ and $\eta(G \lor K_2)=3$. On the other hand, there are graphs $G$ such that $\eta(G \lor K_q) = \max \{ \eta(G), q \}$ for any $q$. An example is the family of stable graphs. In that case, $G \lor K_q$ is called complete split. In the next section, we prove that the additive chromatic number of complete splits is $q$.

![A counterexample for $q = 2$.](W63.eps)

\[CONTRAEJEMPLO\]

The theorem also shows that if the conjecture holds for a graph $G$ then it still holds for $G \lor K_q$ (with $q \leq n-\Delta-1$) since $\chi(G \lor K_q) = \chi(G) + q$.\
A vertex $v$ is *universal* in a graph $G$ when $N(v) = V(G) \backslash \{v\}$. We will use a simplified version of Theorem \[UNIVERTICES\] for solving ACP on known families of graphs having a single universal vertex:

If $G$ is a graph without universal vertices, $\eta(G \lor K_1) = \eta(G)$.

Let $n$ be an integer such that $n \geq 3$. A $n$-*fan* is defined as $F_n = P_{n+1} \lor K_1$ where $P_{n+1}$ is a path of length $n$. Since $\eta(P_{n+1}) = 2$ (see [@ORLOW]), $\eta(F_n) = 2$.

Let $n, m$ be integers such that $n \geq 3$, $m \geq 2$. The *windmill* graph $W_n^m$ is defined as $m$ copies of $K_n$ which share a single vertex, $W_n^m = m K_{n-1} \lor K_1$. Then, $\eta(W_n^m) = n-1$.

Let $n$ be an integer such that $n \geq 4$. A *wheel* is defined as $W_n = C_n \lor K_1$, where $C_n$ is a circuit of $n$ vertices. In order to know $\eta(W_n)$ we first need to know $\eta(C_n)$. Although there already exists a manuscript written by Akbari, Assadi, Emamjomeh-Zadeh and Khani giving the additive chromatic number of circuits, here we propose a different and short proof of it for the sake of completeness.

Let $n \geq 4$. If $n$ is even, then $\eta(C_n) = 2$. Otherwise, $\eta(C_n) = 3$.

If $n$ is even, $C_n$ is a regular bipartite graph and we can use Corollary \[REGULARBIP\]. So, we prove that $\eta(C_n) = 3$ for $n$ odd. Let $V = \{v_1, \ldots, v_n\}$ and suppose that $f:V \rightarrow \{1,2\}$ is an additive 2-coloring of $C_n$. Then, $f$ is also a topological additive 2-numbering of a certain digraph $D$ such that $G(D) = C_n$. Observe that $f(N(v)) \in \{2,3,4\}$ for all $v \in V$. Since $C_n$ is not bipartite, there must be an oriented path of 3 consecutive vertices in $D$. W.l.o.g. assume that $f(N(v_2)) < f(N(v_3)) < f(N(v_4))$. Then, $f(v_1) + f(v_3) = f(N(v_2)) = 2$ and we obtain $f(v_3) = 1$. But, $f(v_3) + f(v_5) = f(N(v_4)) = 4$ giving $f(v_5) = 3$ which is an absurd. Therefore, $\eta(C_n) \geq 3$.

Consider the assignment $f:V \rightarrow [3]$ such that $f(v_2) = f(v_4) = f(v_5) = 1$, $f(v_1) = 2$, $f(v_3) = 3$ and, if $n \geq 7$, then for $i \geq 6$, $f(v_i) = 1$ if $i$ is even and $f(v_i) = 3$ if $i$ is odd. We obtain $f(N(v_1)) = 2$ if $n=5$ and $f(N(v_1)) = 4$ otherwise, $f(N(v_2)) = 5$, $f(N(v_3)) = 2$, $f(N(v_4)) = 4$ and $f(N(v_n)) = 3$. If $n \geq 7$, $f(N(v_5)) = 2$ and $f(N(v_6)) = 4$. If $n \geq 9$, then for $i \in \{7,\ldots,n-1\}$, $f(N(v_i)) = 2$ if $i$ is odd and $f(N(v_i)) = 6$ if $i$ is even. Thus, $f$ is an additive 3-coloring of $C_n$.

Now, $\eta(W_n) = 2$ if $n$ is even and $\eta(W_n) = 3$ otherwise.

Split graphs
============

A graph $G=(V,E)$ is a *split graph* if $V$ can be partitioned in subsets $Q,S$ such that $Q$ is a clique of $G$ and $S$ is a stable set of $G$. We denote vertices of $Q$ with $u_1,\ldots,u_q$ and vertices of $S$ with $v_1,\ldots,v_s$. W.l.o.g. we assume that $Q$ is maximal (unless stated otherwise). The following result states an upper bound of the additive chromatic number of split graphs.

\[COTASUPSPLIT\] Let $G = (Q \cup S, E)$ be a split graph where $Q$ is maximal and $T \subset Q$ be a non-empty set such that the degrees of each vertex of $T$ differ each other. Then, $\eta(G) \leq |Q|-|T|+1$.

W.l.o.g. let $T = \{u_{q-t+1},u_{q-t+2},\ldots,u_{q-1}, u_q\}$ where $t = |T|$. We exhibit an additive $(q-t+1)$-coloring of $G$. Consider the assignment $f:V \rightarrow [q-t+1]$ such that $f(u_i) = i$ for all $i \in [q-t]$, $f(w) = q-t+1$ for all $w \in T \cup S$. We first check for edges between the clique and the stable set. Let $(u_i, v) \in E$. Since $Q$ is maximal, for each $v \in S$, there exists $u(v) \in Q$ such that $v$ is not adjacent to $u(v)$. Then, $f(N(v)) \leq f(Q) - f(u(v)) \leq f(Q) - 1$. On the other hand, let $r_i = |N(u_i) \cap S|$ for all $i \in [q]$. Since $v \in N(u_i)$, $r_i \geq 1$ and $f(N(u_i)) = f(Q) - f(u_i) + (q-t+1).r_i \geq f(Q)$. Therefore, $f(N(u_i)) > f(N(v))$.

Now, we check for edges into the clique. First consider an edge $(u_j, u_k)$ such that $u_j, u_k \in T$. Then, $r_j \neq r_k$ and $f(N(u_j)) = f(Q) - (q-t+1) + (q-t+1).r_j \neq f(Q) - (q-t+1) + (q-t+1).r_k = f(N(u_k))$. Finally consider an edge $(u_j, u_k)$ such that $j \in [q-t]$ and $j < k$. Let $\alpha = f(u_k) - f(u_j)$. Note that $1 \leq \alpha \leq q-t$. Then, $f(N(u_j)) - f(N(u_k)) = \alpha + (q-t+1).(r_j - r_k)$. Suppose that $(q-t+1).(r_j - r_k) = \alpha$. Hence, $1 \leq (q-t+1).(r_j - r_k) \leq q-t$. This contradicts $r_j - r_k \in \bbbz$. Therefore, $f(N(u_j)) \neq f(N(u_k))$.

Observe that $\eta(G) \leq |Q| \leq \chi(G)$, so the conjecture holds for split graphs.\
The bound given in Theorem \[COTASUPSPLIT\] is tight on several families of graphs. We give three of them.

-   *Splits graphs with additive 1-coloring*: Let $G$ be a split graph with maximal clique $Q$ and maximal set $T \subset Q$ having vertices with different degree. Then, $T=Q$ characterizes those graphs with additive 1-coloring: $T=Q$ implies $\eta(G) = 1$ by Theorem \[COTASUPSPLIT\] while the converse is obtained by Observation \[ADDITIVE1\].

-   *Splits graphs with maximal clique of size 2*: Let $G = (Q \cup S, E)$ with $Q = \{u, u'\}$, $S = \{v_1,\ldots,v_r,v'_1,\ldots,v'_t\}$ and $E = \{(u, u')\} \cup \{(u,v_i) : i \in [r]\} \cup \{(u',v'_i) : i \in [t]\}$. If $r \neq t$, we are in the previous case. If $r = t$, $\eta(G) = 2$ which is the value given by Theorem \[COTASUPSPLIT\].

-   *Complete splits*: Let $G = (Q' \cup S', E)$ with $|Q'| \geq 1$, $|S'| \geq 2$, $Q'$ is a clique of $G$ and there are edges $(u, v)$ for all $u \in Q'$ and $v \in S'$. $G$ is known as *complete split*. Since $G$ has $|Q'|$ true twins, $\eta(G) \geq |Q'|$. On the other hand, let $v \in S'$ and $Q = Q' \cup \{v\}$. Here, $Q$ is a maximal clique of $G$. Consider $T = \{u, v\}$ where $u \in Q'$. In virtue of Theorem \[COTASUPSPLIT\], $\eta(G) = |Q|-1 = |Q'|$.

Now, we will see families of split graphs where the bound given by Theorem \[COTASUPSPLIT\] is not tight. We study two of them here and another one in the next section (called complete suns).

A *thin headless spider* of orden $q \geq 2$ is a split graph where $|Q|=|S|=q$ and the set of edges between $Q$ and $S$ is $\{(u_i, v_i) ~:~ i \in [q] \}$. A *thick headless spider* of orden $q \geq 2$ is a split graph where $|Q|=|S|=q$ and the set of edges between $Q$ and $S$ is $\{(u_i, v_j) ~:~ i,j \in [q],~ i \neq j \}$. Equivalently, a thick headless spider is the complement of a thin headless spider of the same order and vice-versa.

Let $G$ be a thin/thick headless spider of order $q$. Then, $$\eta(G) = \biggl\lceil \dfrac{q+1}{2} \biggr\rceil.$$

For the sake of simplicity, we call $r = \lceil \frac{q+1}{2} \rceil$. We start by proving $\eta(G) = r$ when $G$ is thin. Note that $d(u_i) = q$ for all $i$. In virtue of Corollary \[COTAINF\], we have $\eta(G) \geq r$. Then, we only need to propose an additive $r$-coloring of $G$. If $q = 2$, consider the additive 2-coloring $f$ such that $f(u_1) = f(u_2) = f(v_1) = 1$ and $f(v_2) = 2$. If $q \geq 3$, consider the assignment $f:V \rightarrow [r]$ such that $f(u_i) = r - i + 1$ and $f(v_i) = 1$ for all $i \in [r]$, and $f(u_i) = q - i + 1$ and $f(v_i) = \lfloor \frac{q+1}{2} \rfloor$ for all $i \in \{r+1,\ldots,q\}$. We obtain $f(N(u_i)) = f(Q) - f(u_i) + f(v_i) = f(Q) - r + i$ for all $i \in [q]$. Then, for $j < k$, we have $f(N(u_j)) < f(N(u_k))$. Regarding the edge $(u_i, v_i)$, we first analyze when $i = 1$. Note that $f(u_1) = r$, $f(u_2) = r - 1$ and $f(u_q) = 1$, then $f(N(u_1)) = f(Q) - r + 1 \geq f(u_1) + f(u_2) + f(u_q) - r + 1 = r + 1 > r = f(N(v_1))$. If $i \geq 2$, $f(N(u_i)) > f(N(u_1)) > f(N(v_1)) = r \geq f(u_i) = f(N(v_i))$.

Now, we consider that $G$ is thick. If $q = 2$ then $G$ is isomorphic to a thin headless spider of order 2. Hence, assume that $q \geq 3$. Consider the assignment $f:V \rightarrow [r]$ such that $f(u_i) = i$ and $f(v_i) = 1$ for all $i \in [r]$, and $f(u_i) = r$ and $f(v_i) = i-r+1$ for all $i \in \{r+1,\ldots,q\}$. We obtain $f(N(u_i)) = f(V) - f(u_i) - f(v_i) = f(V) - i - 1$ for all $i \in [q]$. Then, for $j < k$, we have $f(N(u_j)) > f(N(u_k))$. Regarding the edge $(u_i, v_i)$, note first that $Q \subsetneqq V \backslash \{v_i\}$. Hence, $f(N(v_i)) = f(Q) - f(u_i) < f(V \backslash \{v_i\}) - f(u_i) = f(N(u_i))$.\
We finish by proving that $\eta(G) \geq r$. Suppose that there exists an additive $(r-1)$-coloring $f$ of $G$. Recall that $f(N(u_i)) = f(V) - f(u_i) - f(v_i)$ for all $i \in [q]$. Thus, $f(V) - (2r-2) \leq f(N(u_i)) \leq f(V) - 2$. Since there are $2r-3$ integers in the range of feasible values for $f(N(u_i))$ and $2r-3 < q$, there are two indexes $j$ and $k$ such that $f(N(u_j))=f(N(u_k))$ by the pigeonhole principle, leading to a contradiction.

Suns
====

Let $G$ be a graph and $U = \{u_1, \ldots, u_m\} \subset V(G)$. A *sun* is a graph $G'$ with $V(G') = V(G) \cup V$ where $V = \{v_1, \ldots, v_m\}$ and $$E(G') = E(G) \cup \{(u_i, v_{i-1}), (u_i, v_i) ~:~ i \in [m] \}.$$ For the sake of simplicity, $u_0$ and $v_0$ are another names for vertices $u_m$ and $v_m$.

In this section, we study *cycle suns* $CS_m$, when $G$ is a circuit ($V(G) = U$ and $E(G) = \{ (u_i, u_{i-1}) ~:~ i \in [m] \}$), *wheel suns* $WS_m$, when $G$ is a wheel ($V(G) = U \cup \{w\}$ and $E(G) = \{ (u_i, u_{i-1}), (u_i, w) ~:~ i \in [m] \}$), and *complete suns* $KS_m$, when $G$ is a complete graph of size $m$.

Let $m \geq 4$. Then, $\eta(CS_m) = \eta(WS_m) = 2$.

By Observation \[ADDITIVE1\], $\eta(CS_m) \geq 2$ and $\eta(WS_m) \geq 2$ so we only have to propose an additive 2-coloring of $CS_m$ and $WS_m$. We start with $CS_m$.

Consider an assignment $f:V \rightarrow \{1,2\}$ such that $f(u_i) = 2$ if $i$ is odd, $f(u_i) = 1$ if $i$ is even and $f(v) = 1$ for all $v \in V \backslash \{v_1\}$. If $m$ is even, also assign $f(v_1) = 1$. Thus, $f(N(u_i)) = 4$ if $i$ is odd, $f(N(u_i)) = 6$ if $i$ is even and $f(N(v)) = 3$ for all $v \in V$. If $m$ is odd, assign $f(v_1) = 2$. In this case, $f(N(u_1)) = 6$, $f(N(u_2)) = 7$, $f(N(u_m)) = 5$ and for $i = 3,\ldots,m-1$, $f(N(u_i)) = 4$ if $i$ is odd and $f(N(u_i)) = 6$ if $i$ is even. In addition, $f(N(v_m)) = 4$ and $f(N(v)) = 3$ for all $v \in V \backslash \{v_m\}$. Therefore, $f$ is an additive 2-coloring of $CS_m$.

For $WS_m$, assume that $m \neq 5$ and consider the same assignment as before plus $f(w) = 1$. Then, values of $f(N(v))$ remains the same as in $CS_m$, values of $f(N(u))$ are the same as in $CS_m$ plus one, $f(N_{WS_m}(u)) = f(N_{CS_m}(u))+1$, and $f(N(w)) = \lceil 3m/2 \rceil$. If $m = 4$, clearly $f$ is an additive 2-coloring of $WS_4$. If $m \geq 6$, $f(N(w)) > 8 \geq f(N(u))$ and $f$ is an additive 2-coloring of $WS_m$.

For $m = 5$, we propose a different additive 2-coloring of $WS_5$: $f(u_1) = f(u_2) = f(u_4) = f(v_4) = f(v_5) = 1$, $f(u_3) = f(u_5) = f(v_1) = f(v_2) = f(v_3) = f(w) = 2$. Then, $f(N(v_1)) = 2$, $f(N(v_2)) = 3$, $f(N(u_5)) = 6$, $f(N(w)) = 7$, $f(N(u_1)) = f(N(u_3)) = 8$, $f(N(u_2)) = f(N(u_4)) = 9$.

Let $m \geq 3$. Then, $\eta(KS_m) = \bigl\lceil \frac{m+2}{3} \bigr\rceil.$

For the sake of simplicity, we call $r = \lceil \frac{m+2}{3} \rceil$. Note that $d(u_i) = m+1$ for all $i$. In virtue of Corollary \[COTAINF\], we have $\eta(G) \geq r$.

We only have to propose an additive $r$-coloring of $KS_m$. First, define a permutation function $\mathfrak{p}:[m] \rightarrow [m]$ as follows: $\mathfrak{p}(1) = 1$, $\mathfrak{p}(j) = \frac{j}{2} + 1$ for $j = 2,\ldots,m$ and $j$ even, $\mathfrak{p}(j) = m - \frac{j-3}{2}$ for $j = 3,\ldots,m$ and $j$ odd. Clearly, its inverse is: $\mathfrak{q}(1) = 1$, $\mathfrak{q}(i) = 2(i-1)$ for $i = 2,\ldots,\lfloor \frac{m}{2} \rfloor + 1$, $\mathfrak{q}(i) = 3 + 2(m-i)$ for $i = \lfloor \frac{m}{2} \rfloor + 2,\ldots,m$. Let $f$ be the following assignment: $$f(u_i) = \begin{cases}
   r,             & m \equiv 2~ (\textrm{mod}~3) ~\land~ i = \mathfrak{p}(m), \\
   \biggl\lfloor \dfrac{\mathfrak{q}(i)}{3} \biggr\rfloor + 1,             & \textrm{otherwise}.
\end{cases}$$ $$f(v_i) = \begin{cases}
   r + 1 - \biggl\lceil \dfrac{\mathfrak{q}(i)}{3} \biggr\rceil,   & i = 1 ~\lor~ i \geq \biggl\lfloor \dfrac{m}{2} \biggr\rfloor + 2, \\
   2,                                                              & m \equiv 2~ (\textrm{mod}~6) ~\land~ i = \mathfrak{p}(m), \\
   r + 1 - \biggl\lceil \dfrac{\mathfrak{q}(i)+2}{3} \biggr\rceil, & \textrm{otherwise}.
\end{cases}$$ It is easy to check that $f(w) \in [r]$ for all $w \in U \cup V$. Also, observe that first and second case in the definition of $f(v_i)$ do not overlap: if $m \equiv 2~ (\textrm{mod}~6)$, $m$ is even and, therefore, $2 \leq \mathfrak{p}(m) = m/2 + 1 < \lfloor \frac{m}{2} \rfloor + 2$.

We claim that $f(v_i)$ satisfies the following recursive relationship: $$f(v_i) = 2r - \mathfrak{q}(i) + f(u_i) - f(v_{i-1}),~~~ \forall~ i \in [m].$$ Then, $f(N(u_i)) = f(U) - f(u_i) + f(v_i) + f(v_{i-1}) = f(U) + 2r - \mathfrak{q}(i)$ for all $i$. Since $\mathfrak{q}$ is injective, $f(N(u_i)) \neq f(N(u_k))$ for all $i \neq k$. Regarding edges between $U$ and $V$, note that $f(U) > m$ and for any $v \in V$, $v$ has degree 2, then $f(N(v)) \leq 2r < f(U) + 2r - m \leq f(U) + 2r - \mathfrak{q}(i) = f(N(u_i))$ for all $i$. Therefore, $f$ is an additive $r$-coloring of $KS_m$.

Now, we check our claim. If $i \neq \mathfrak{p}(m) = \lceil \frac{m}{2} \rceil + 1$ or $m \not\equiv 2~ (\textrm{mod}~3)$, then $f(u_i) - \mathfrak{q}(i) = 1 - \lceil \frac{2\mathfrak{q}(i)}{3} \rceil$. That is, we have to check $f(v_i) = 2r + 1 - \lceil \frac{2\mathfrak{q}(i)}{3} \rceil - f(v_{i-1})$. In the case that $m \equiv 2~ (\textrm{mod}~3)$ and $i = \mathfrak{p}(m) = \lceil \frac{m}{2} \rceil + 1$, $f(u_i) - \mathfrak{q}(i) = r - m$ and we have to check $f(v_i) = 3r - m - f(v_{i-1})$.

1.  Case $i = 1$: Since $f(v_0) = f(v_m) = r$, $f(v_1) = r + 1 - \lceil \frac{1}{3} \rceil = 2r + 1 - \lceil \frac{2}{3} \rceil - r$.

2.  Case $i = 2$: Since $f(v_1) = r$, $f(v_2) = r + 1 - \lceil \frac{4}{3} \rceil = 2r + 1 - \lceil \frac{4}{3} \rceil - r$.

3.  Case $i = 3,\ldots,\lfloor \frac{m}{2} \rfloor$ or “$i = \lfloor \frac{m}{2} \rfloor + 1$ when $m \not\equiv 2~ (\textrm{mod}~6)$”: First, we prove $1 - \lceil \frac{2(i-1)+2}{3} \rceil = \lceil \frac{2(i-1)}{3} \rceil - \lceil \frac{4(i-1)}{3} \rceil$. If $i \equiv 1~ (\textrm{mod}~ 3)$, let $h = \frac{i-1}{3}$. Then, $1 - \lceil \frac{2(i-1)+2}{3} \rceil = 1 - 2h - \lceil \frac{2}{3} \rceil
    = 2h - 4h = \lceil \frac{2(i-1)}{3} \rceil - \lceil \frac{4(i-1)}{3} \rceil$. Cases when $i \equiv 0$ or $2~ (\textrm{mod}~ 3)$ are analogous. Since $f(v_{i-1}) = r + 1 - \lceil \frac{2(i-1)}{3} \rceil$, $f(v_i) = r + 1 - \lceil \frac{2(i-1)+2}{3} \rceil = 2r + 1 - \lceil \frac{4(i-1)}{3} \rceil - r - 1 + \lceil \frac{2(i-1)}{3} \rceil$.

4.  Case $i = \lfloor \frac{m}{2} \rfloor + 1$ when $m \equiv 2~ (\textrm{mod}~6)$: Then, $r = \lceil \frac{m+2}{3} \rceil = \frac{m}{3} + 1$, $\mathfrak{q}(i) = m$, $\mathfrak{q}(i-1) = m-2$, $f(v_{i-1}) = r + 1 - \lceil\frac{m-2+2}{3}\rceil = 1$ and $f(v_i) = 2 = 3r - m - 1$.

5.  Case $i = \lfloor \frac{m}{2} \rfloor + 2$: If $m$ is even, $\mathfrak{q}(i) = m - 1$ and $\mathfrak{q}(i-1) = m$. If $m \not\equiv 2~ (\textrm{mod}~3)$, $f(v_{i-1}) = r + 1 - \lceil \frac{m+2}{3} \rceil = 1$. Note that $2r - \lceil \frac{2(m-1)}{3} \rceil = 2$. If $m \equiv 2~ (\textrm{mod}~3)$, then $m \equiv 2~ (\textrm{mod}~6)$ and, therefore, $f(v_{i-1}) = 2$ and $2r - \lceil \frac{2(m-1)}{3} \rceil = 3$. Then, $f(v_i) = r + 1 - \lceil \frac{m - 1}{3} \rceil = 2 = 2r + 1 - \lceil \frac{2(m - 1)}{3} \rceil - f(v_{i-1})$; If $m$ is odd, $\mathfrak{q}(i) = m$ and $\mathfrak{q}(i-1) = m-1$, If $m \not\equiv 2~ (\textrm{mod}~3)$, note that $1 - \lceil \frac{m}{3} \rceil = \lceil \frac{m+1}{3} \rceil - \lceil \frac{2m}{3} \rceil$. Then, $f(v_i) = r + 1 - \lceil \frac{m}{3} \rceil = 2r + 1 - \lceil \frac{2m}{3} \rceil - r - 1 + \lceil \frac{m-1+2}{3} \rceil$. If $m \equiv 2~ (\textrm{mod}~3)$, $r - 1 = \lceil \frac{m+2}{3} \rceil - 1 = \lceil \frac{m+1}{3} \rceil = \lceil \frac{m}{3} \rceil$ and $f(v_{i-1}) = r + 1 - \lceil \frac{m-1+2}{3} \rceil = 2$. Then, $f(v_i) = r + 1 - \lceil \frac{m}{3} \rceil = 2 = 3r - m - f(v_{i-1})$.

6.  Case $i = \lfloor \frac{m}{2} \rfloor + 3, \ldots, m-1$: We have $f(v_i) = r + 1 - \lceil \frac{3 + 2(m-i)}{3} \rceil$ and $2r + 1 - \lceil \frac{2\mathfrak{q}(i)}{3} \rceil - f(v_{i-1}) =
    r - \lceil \frac{6 + 4(m-i)}{3} \rceil + \lceil \frac{3 + 2(m-i+1)}{3} \rceil$. To prove that both expressions are equal, we proceed as in the third case.

**An integer programming formulation for ACP.** As far as we know, there is no tools available for solving ACP. However, we can solve instances of this problem by modeling it as an integer linear programming formulation and using an available solver (in our case, CPLEX 12.6 have been used).

Let $G = (V,E)$ be a graph, $E_2 = \{(u,v), (v,u) : (u,v) \in E\}$ (edges occur in both directions), integer variables $k$ and $f(v)$ for all $v \in V$, and binary variables $z(u,v)$ for all $(u,v) \in E_2$, where $z(u,v) = 1$ if and only if $f(N(u)) < f(N(v))$. The following formulation computes $\eta(G)$:

$$\begin{aligned}
\min k & & \notag \\
\textrm{subject to} & & \\
 & f(N(u)) - f(N(v)) + M_{uv} z(u,v) \leq M_{uv} - 1, & \forall~~(u,v) \in E_2 \\
 & z(u,v) + z(v,u) = 1, & \forall~~(u,v) \in E \\
 & 1 \leq f(v) \leq UB, & \forall~~v \in V \\
 & f(v) \leq k, & \forall~~v \in V \\
 & z(u,v) \in \{0, 1\}, & \forall~~(u,v) \in E_2 \\
 & k, f(v) \in \bbbz_+, & \forall~~v \in V\end{aligned}$$

where $M_{uv} = 1+|N(u)\backslash N(v)|UB - |N(v)\backslash N(u)|$ for all $(u,v) \in E_2$ and $UB$ is an upper bound of $\eta(G)$.

We also propose additional inequalities. They are considered whenever possible in order to improve the performance of the optimization. On the one hand, the initial relaxation can be reinforced by adding these valid inequalities: $$z(v,w) + z(w,u) \leq 1,~~~ \textrm{for all}~ u,v,w~ \textrm{such that}~ (u,v) \notin E_2,~ w \in N(u) \subset N(v).$$ In fact, if $z(v,w) = z(w,u) = 1$, then $f(N(v)) < f(N(w)) < f(N(u))$ which leads to a contradiction.

On the other hand, symmetrical solutions arising from the presence of twin vertices can be partially removed as follows. Let $\mathscr{C}$ be a partition of $V$, where each element of $\mathscr{C}$ can be: 1) a single vertex, 2) two or more false twins each other, and 3) two or more true twins each other. Then, for every set of false twins $\{v_1, \ldots, v_t\} \in \mathscr{C}$ add inequalities $f(v_i) \leq f(v_{i+1}),~~\forall~i \in [t-1]$ and remove variables $z(u,v_i)$, $z(v_i,u)$ and constraints where they occur for all $i \in 2,\ldots,t$ and $u \in N(v_1)$. Analogously, for every set of true twins $\{v_1, \ldots, v_t\} \in \mathscr{C}$ add inequalities $f(v_i) \leq f(v_{i+1}) - 1,~~\forall~i \in [t-1]$ and remove variables $z(v_i, v_j)$ and constraints where they occur for all $i,j = 2,\ldots,t$ such that $i \neq j$.

The following procedure generates a suitable partition $\mathscr{C}$. First, compute a partition $\mathscr{C}$ of $V$ into maximal sets of true twins. Let $\mathscr{C}_1 \subset \mathscr{C}$ composed only of singleton sets and $V' = \bigcup_{W \in \mathscr{C}_1} W$ ($V' = \{ v \in V : \{v\} \in \mathscr{C} \}$). Then, compute a partition $\mathscr{C'}$ of $V'$ into maximal sets of false twins. Finally, do $\mathscr{C} \leftarrow (\mathscr{C} \backslash \mathscr{C}_1) \cup \mathscr{C'}$. We implemented a tool for solving ACP based on this formulation. It can be downloaded from `http://www.fceia.unr.edu.ar/\simdaniel/stuff/acp.zip`.\
Besides this tool have been very useful for checking our theoretical results, we have tested the conjecture with it over all connected graphs up to 10 vertices (about 12 million graphs). Instances are provided by Brendan McKay (`http://users.cecs.anu.edu.au/\simbdm/data/graphs.html`) and a DSATUR code by Rhyd Lewis (`http://rhydlewis.eu/resources/gCol.zip`) have been used for obtaining $\chi(G)$.\
**Acknowledgements.** I wish to thank Dr. Graciela Nasini for their helpful comments. This work is partially supported by grants PID-UNR 416, PICT-2013-0586 and PIP-CONICET 11220120100277.

[10]{}\[bibliography\]

Karpovsky M.G., Chakrabarty K., Levitin L.B.: On a new class of codes for identifying vertices in graphs. IEEE Trans. Inf. Theory **44**, 599–611 (1998)

Chartrand G., Lesniak L., VanderJagt D. W., Zhang P.: Recognizable Colorings of Graphs. Discussiones Mathematicae Graph Theory **28**, 35–57 (2008)

Esperet L., Gravier S., Montassier M., O. Pascal, Parreau A.: Locally identifying coloring of graphs. Electron. J. Combin. **19**(2), \#P40 (2012)

Seamone B.: *The 1-2-3 Conjecture and related problems: a survey*, Manuscript.\
`http://arxiv.org/abs/1211.5122`

Czerwiński S., Grytczuk J., Zelazny W.: Lucky labelings of graphs. Inform. Process. Lett. **109**, 1078–1081 (2009)

A. Ahadi, A. Dehghan and E. Mollaahmadi, *On the Lucky Labeling of Graphs*, Manuscript.  `http://arxiv.org/abs/1007.2480`

Orlow N.: Advances in Lucky Labelling graphs, Fibsum graphs, and 3-regular graph decompositions. Research Experiences for Graduate Students, August 2009.

Grappe R., Grippo L. N., Valencia-Pabon M.: Lucky number of bounded-treewidth graphs. Tech. Rep. LIPN 2012, submitted to the WG 2012 conference.

Ahadi A., Dehghan A., Kazemi M., Mollaahmadi E.: Computation of lucky number of planar graphs is NP-hard. Inform. Process. Lett. **112**, 109–112 (2012)

Akbari S., Ghanbari M., Manaviyat R., Zare S.: On the Lucky Choice Number of Graphs. Graphs and Combinatorics **29**, 157–163 (2013)

Grytczuk J., Bartnicki T., Czerwiński S., Bosek B., Matecki G., Zelazny W.: Additive colorings of planar graphs. Graphs and Combinatorics **30**, 1087–1098 (2014)

Brandt A., Diemunsch J., Jahanbekam S.: Lucky Choice Number of Planar Graphs with Given Girth. Manuscript.\
`http://math.ucdenver.edu/\simsjahanbekam/Lucky.pdf`

Miller M., Rajasingh I., Emilet D. A., Jemilet D. A.: d-Lucky Labeling of Graphs. Procedia Computer Science (ICRTC-2015) **57**, 766–771 (2015)

J. Marenco, M. Mydlarz and D. Severín, *Topological Additive Numbering of Directed Acyclic Graphs*, Inform. Process. Lett. **115**, 199–202 (2015)
