Injective Colorings with Arithmetic Constraints

Abstract

An injective coloring of a graph is a vertex labeling such that two vertices sharing a common neighbor get different labels. In this work we introduce and study what we call additive  colorings. An injective coloring $c:V(G)\rightarrow \mathbb {Z}$ of a graph $G$ is an additive coloring if for every $uv, vw$ in $E(G)$, $c(u)+c(w)\ne 2c(v)$. The smallest integer $k$ such that an injective (resp. additive) coloring of a given graph $G$ exists with $k$ colors (resp. colors in $\{1,\ldots ,k\}$) is called the injective (resp. additive) chromatic number (resp. index). They are denoted by $\chi _i(G)$ and $\chi '_a(G)$, respectively. In the first part of this work, we present several upper bounds for the additive chromatic index. On the one hand, we prove a super linear upper bound in terms of the injective chromatic number for arbitrary graphs, as well as a linear upper bound for bipartite graphs and trees. Complete graphs are extremal graphs for the super linear bound, while complete balanced bipartite graphs are extremal graphs for the linear bound. On the other hand, we prove a quadratic upper bound in terms of the maximum degree. In the second part, we study the computational complexity of computing $\chi '_a(G)$. We prove that it can be computed in polynomial time for trees. We also prove that for bounded treewidth graphs, to decide whether $\chi '_a(G)\le k$, for a fixed $k$, can be done in polynomial time. On the other hand, we show that for cubic graphs it is NP-complete to decide whether $\chi '_a(G)\le 4$. We also prove that for every $\epsilon >0$ there is a polynomial time approximation algorithm with approximation factor $n^{1/3+\epsilon }$ for $\chi '_a(G)$, when restricted to split graphs. However, unless $\mathsf P =\mathsf NP$, for every $\epsilon >0$ there is no polynomial time approximation algorithm with approximation factor $n^{1/3-\epsilon }$ for $\chi '_a(G)$, even when restricted to split graphs.

1 Introduction

In this work, all graphs under consideration are finite and simple. An injective coloring of a graph $G$ is an assignment of colors to the vertices of $G$ such that two vertices sharing a common neighbor get different colors. Injective colorings were introduced in [12]. The smallest integer $k$ such that an injective coloring with $k$ colors exists is called the injective chromatic number of $G$ and it is denoted by $\chi _i(G)$.

In this work, we introduce another concept which we call additive coloring. An additive  coloring $c$ of a graph $G=(V,E)$ is a function assigning positive integers to its vertices such that by assigning to each edge $uv$ the value $|c(u)-c(v)|$, we obtain a proper edge coloring $\tilde{c}$ of $G.$ In order to ease the presentation we set

$$\begin{aligned}{}[k]:=\{1,\ldots ,k\}. \end{aligned}$$

The smallest integer $k$ such that an additive  colorings exists with colors in the set $[k]$ is called the additive  chromatic index of $G$. We denote it by $\chi '_a(G)$. If an additive  coloring $c$ uses colors in the set $[k]$, then the associated proper edge coloring $\tilde{c}$ uses colors in the set $[k-1]\cup \{0\}$. Hence, we have that $\chi '(G)\le \chi '_a(G)$, where $\chi '(G)$ is the chromatic index of $G$.

Notice that $c$ is an additive coloring if and only if for every three distinct vertices $x,y,z$ with $xy,yz \in E$, the following two properties hold: $c(x)\ne c(z)$, and $c(x)+c(z)\ne 2c(y)$. Hence, additive colorings are injective colorings. Then, $\Delta (G)\le \chi _i(G)\le \chi '_a(G)$, as any additive  coloring using colors in the set $[k]$ is an injective coloring with at most $k$ colors. We shall see throughout this work that these two parameters are closely related and that the additive structure of integers is closely related with the existence of additive colorings.

2 Upper Bounds

We start by showing a general upper bound of $\chi '_a(G)$ in terms of $\chi _i(G)$.

Proposition 1

Let $G$ be a graph. Then

$$\begin{aligned} \chi '_a(G)\le \chi '_a(K_{\chi _i(G)}), \end{aligned}$$

where $K_m$ denotes the complete graph on $m$ vertices.

Proof

Let $m=\chi _i(G)$. We assume that the set of vertices of the complete graph $K_m$ is the set $[m]$. Let $c$ be an additive coloring of $K_m$ with maximum value $l$. Then, given any three distinct vertices $i,j,k$ in $[m]$, the colors $c(i),c(j)$ and $c(k)$ are distinct, and $c(i)+c(j)\ne 2c(k)$.

Let $c'$ be an injective coloring of $G$ with $m$ colors so that for each $n\in V(G), c'(n)\in V(K_m)=[m]$. Then, given any three distinct vertices $u,v,w$ in $G$, with $u$ and $w$ neighbors of $v$, we have that $c'(u)\ne c'(w)$.

If $c'(v)\in \{c'(u),c'(w)\}$, then $c(c'(u))+c(c'(w))\ne 2c(c'(v))$. Otherwise, $c'(u),c'(v),c'(w)$ are distinct and $c(c'(u))+c(c'(w))\ne 2c(c'(v))$. Hence, by defining $c''(u):=c(c'(u))$ for every vertex $u$, we obtain an additive coloring of $G$ with maximum value $l$. $\square$

Obviously, this upper bound is tight for complete graphs as $\chi _i(K_m)=m$. We remark that a set of integers defines an additive coloring of $K_m$ if and only if it does not contain arithmetic progressions of length three. Hence, in order to effectively apply the upper bound given in Proposition 1, we need some information about the smallest integer $l$ such that there is a set of $m$ integers without arithmetic progression of length three and contained in $[l]$. The determination of this value, in our terms $\chi '_a(K_m)$, has been the focus of research for more than 70 years, initiated in [7] where the first upper bound on $m$ in terms of $l$ was given, which was later improved in [13, 17, 18, 20]. Currently, the best upper bound appears in [2]. On the other hand, the first lower bound was proved in [1] and it was later improved in [6]. These best bounds can be stated as follows: there are constants $c_1$ and $c_2$ such that

$$\begin{aligned} c_1 l\sqrt{\frac{\log ^{\frac{1}{8}} l}{2^{4\sqrt{2 \log l}}}} \le m \le c_2 l \sqrt{\frac{\log \log l}{\log l}}. \end{aligned}$$

(1)

In [10] the exact value of $\chi '_a(K_m)$ ¹, for $m\le 41$, was computed, and lower and upper bounds, for $m\le 100$, were given (see Table 1).

Table 1 $\chi '_a(K_m)$ for $m\le 40$, [10]

By doing some standard calculus manipulations, from Proposition 1 and Inequality 1 we get the following super linear upper bound for $\chi '_a(G)$. This bound will be applied later to obtain some (in)approximability results for the computation of the additive chromatic index.

Theorem 2

There is a constant $c$ such that, for each graph $G$ we have $\chi '_a(G)\le \chi _i(G)g(\chi _i(G)),$ where $g(x)=c2^{\sqrt{2\log (x)}}$.

One can see that the injective chromatic number of a graph $G$ is the chromatic number of the graph $G^{(2)}$, obtained from $G$ by adding edges between vertices at distance two and by removing all the original edges. When $G$ is a bipartite graph with independent sets $U$ and $W$, the graph $G^{(2)}$ is the disjoint union of the graphs $G^U=G^2[U]$ and $G^W=G^2[W]$ induced by the independent sets $U$ and $W$ of $G$ in $G^{(2)}$, respectively. Then, for bipartite graphs we have the following [12].

$$\begin{aligned} \chi _i(G)=\max \{\chi (G^U),\chi (G^W)\}. \end{aligned}$$

(2)

A similar result holds for the additive chromatic index which allows us to get a linear upper bound for $\chi '_a(G)$ in terms of $\chi _i(G)$, for bipartite graphs. In the sequel, $N_G(u)$ denotes the set of neighbors of a vertex $u$ in a graph $G$.

Theorem 3

Let $G$ be a bipartite graph. Then,

$$\begin{aligned} \chi '_a(G)\le 2\chi _i(G)-1. \end{aligned}$$

Proof

Let $G$ be a bipartite graph with independent sets $U$ and $W$. Let $G^U$ and $G^W$ defined as above. Let $k_U:=\chi (G^U)$ and $k_W:=\chi (G^W)$. Let $c$ and $c'$ be proper vertex colorings of $G^U$ and $G^W$, respectively such that $c(u)\in [k_U]$, for each $u\in G^U$, and $c'(w)\in [k_W]$, for each $w\in G^W$. We define $\varphi :U\cup W\rightarrow \mathbb {N}$ as follows. For each $u\in U$, $\varphi (u)=c(u)$ and $\varphi (v)=c'(v)+k_U-1$, for each $v\in W$. Then $\max \varphi =k_U+k_W-1\le 2\chi _i(G)-1$ and it is easy to see that $\varphi$ is an injective coloring. Hence, in order to prove that $\varphi$ is an additive  coloring we prove that $\varphi (u)+\varphi (v)\ne 2\varphi (w)$ for every $u,v,w$ and $w\in N_G(u)\cap N_G(v)$. When $u,v\in U$, as $c$ is a proper coloring of $G^U$, $\varphi (u)\ne \varphi (v)$ and $\varphi (u),\varphi (v)\le k_U$. Moreover, $\varphi (w)\ge k_U$. Therefore, $\varphi (u)+\varphi (v)\ne 2\varphi (w)$. We now consider the situation for vertices $u,v\in W$. As $c'$ is a proper coloring of $G^W$, $\varphi (u)\ne \varphi (v)$ and $\varphi (u),\varphi (v)\ge k_U$. Moreover, $\varphi (w)\le k_U$. Therefore, $\varphi (u)+\varphi (v)\ne 2\varphi (w)$. $\square$

In the next result we prove that the previous upper bound is tight.

Proposition 4

Let $n$ be odd, with $n\ge 9$. Then, $\chi '_a(K_{n,n})=2n-1$.

Proof

Let $U$ and $W$ be the two independent sets of $K_{n,n}$ each of size $n$. It is clear that both $(K_{n,n})^U$ and $(K_{n,n})^W$ are complete graphs of size $n$. Hence, $\chi _i(K_{n,n})=n$.

By coloring $U$ with colors in the set $[n]$ and $W$ with colors in the set $[2n-1]{\setminus } [n-1]$, we get an additive coloring of $K_{n,n}$. Then, $\chi '_a(K_{n,n})\le 2n-1$.

We now prove the lower bound $\chi '_a(K_{n,n})\ge 2n-1$. Let $\varphi$ be an additive  coloring of $K_{n,n}$, and let $A=\varphi (U)$ and $B=\varphi (W)$. Since every vertex in $U$ is adjacent to every vertex in $W$, the function $\varphi$ must be injective when restricted to $U$. Similarly, it must be injective when restricted to $W$. Hence, $|A|=|B|=n$.

In this situation, $\varphi$ is an additive  coloring if and only if $av(A)\cap B=av(B)\cap A=\emptyset$, where $av(C):=\left\{ \frac{x+y}{2}\in \mathbb {N}: x,y\in C, x\ne y\right\} .$ Therefore,

$$\begin{aligned} \max \{|av(A)|,|av(B)|\}+n\le \chi '_a(K_{n,n}). \end{aligned}$$

For the sake of contradiction let us assume that $\chi '_a(K_{n,n})\le 2n-2$. Then, $|av(A)|\le n-2$ and $|av(B)|\le n-2$. We first show that in this situation, $av(B)=\{a,a+1,\ldots ,a+(n-3)\}$, for some integer $a$. To this purpose we need the following property. $\square$

Claim

Let $D$ be a set with all its elements having the same parity. If $|D|\ge 2$, then $|av(D)|\ge 2|D|-3$. Moreover, for $|D|\ge 5$, $|av(D)|=2|D|-3$ if and only if $D$ is an arithmetic progression.

Proof

Without loss of generality we can assume that all elements of $D$ are even integers. The case $|D|=2$ is direct. Let $D=\{a_1<a_2<\ldots <a_k\}$ be the elements of $D$ and let us assume that $k\ge 3$. Let $b_{i,j}:=a_i+a_j$. Then, the following $2k-3$ integers are all distinct and even,

$$\begin{aligned} b_{1,2}<b_{1,3}<b_{2,3}<\ldots < b_{k-2,k}<b_{k-1,k}. \end{aligned}$$

This shows that $|av(D)|\ge 2|D|-3$. Moreover, for each $i\ge 4$ the following two sequences have $2i-3$ integers, all distinct and even.

$$\begin{aligned} b_{1,2}<\cdots <b_{1,i-1}<b_{1,i}<b_{2,i}<\cdots <b_{i-1,i} \end{aligned}$$

and

$$\begin{aligned} b_{1,2}<\cdots <b_{1,i-1}<b_{2,i-1}<b_{2,i}<\cdots <b_{i-1,i}. \end{aligned}$$

Since we can extend each of the above two sequences with $2k-3-(2i-3)$ distinct terms, we get that if $|av(D)|=2|D|-3$ then $b_{1,i}=b_{2,i-1}$ for each $i\ge 4$. From this equality we get $a_1+a_i=a_2+a_{i-1}$ and then $a_2-a_1=a_i-a_{i-1}$, for $i\ge 4$. It is easy to see that the equality $a_2+a_5=a_3+a_4$ holds, when $k\ge 5$. Therefore, $D$ is an arithmetic progression.

We now prove that $av(B)=\{a,a+1,\ldots ,a+(n-3)\}$. As $|B|=n$ is odd, it has a subset $D$ with all its elements having the same parity, and such that $2|D|\ge n+1$. From the claim, it follows that $|av(D)|\ge 2|D|-3$. Since $av(D)\subseteq av(B)$ and $|av(B)|\le n-2$ we conclude that $av(D)=av(B)$ and $|av(D)|=2|D|-3=n-2$. Since $n\ge 9$, we get that $|D|\ge 5$ which again from the claim implies that $D$ is an arithmetic progression. It is clear that in this case $av(D)$, and then $av(B)$, are arithmetic progressions as well.

Let $a,b\ge 1$ integers such that $av(B)=\{a,a+b,\ldots ,a+b(n-3)\}$. Then, $a\ge 2$ and $a+b(n-3)\le 2n-3$. Since $n\ge 9$ we obtain that $b\le 2+1/(n-3)<3$ which implies $b\le 2$. If $b=2$, then the elements in $av(B)$ have the same parity. As we are assuming that $av(B)\cap A=\emptyset$ and that $A\subseteq [2n-2]$, $A$ must contain a set $D'$ of size at least $|av(B)|+1=n-1$ whose elements have the same parity. Again we apply the claim and we get that $av(A)\ge 2(n-1)-3=2n-5>n-2$ which, for $n\ge 9$, contradicts $\chi '_a(K_{n,n})\le 2n-2$. Therefore, we conclude that $b=1$. That is, $av(B)=\{a,a+1,\ldots ,a+(n-3)\}$. Then

$$\begin{aligned} A=\{1,\ldots , a-1\}\cup \{a+n-2,\ldots ,n+n-2\}. \end{aligned}$$

Hence, the set $av(A)$ contains the sets $\{2,\ldots ,a-2\}$, $\{a+n-1,\ldots ,2n-3\}$, and $\mathbb {N}\cap \left\{ \frac{a+n-1+i}{2}:i=0,\ldots ,n-3\right\} .$ Therefore, $av(A)$ has at least $n-4+\lfloor (n-2)/2 \rfloor$ elements which is larger than $n-2$, for $n\ge 9$. This is a contradiction with $\chi '_a(K_{n,n})\le 2n-2$.

We can still improve our previous upper bounds when we consider trees. It is easy to see that for trees the injective chromatic number equals the maximum degree. So Theorem 3 applied to a tree $T$ implies that $\chi '_a(T)\le 2\Delta (T)-1$. It is also clear that this upper bound reduces to $\chi _i(T)=\Delta (T)=\chi '_a(T)$, when $T$ has radius 1. Similarly, when the radius of $T$ is two, we have that $\chi '_a(T)\le \lceil 3/2\Delta \rceil -1$. More generally we have the following.

Proposition 5

Let $T$ be a tree of maximum degree $\Delta$. If $T$ has radius at least three, then

$$\begin{aligned} \chi '_a(T)\le \lceil 5\Delta /3\rceil -1. \end{aligned}$$

Proof

By induction we prove something slightly stronger. $T$ has an additive coloring using colors in the set

$$\begin{aligned} \Omega :=\{1,\ldots ,\Delta +\lceil 2\Delta /3\rceil -1 \}{\setminus } \{\lceil 2\Delta /3\rceil +1,\ldots , \Delta -1 \}. \end{aligned}$$

Let $d$ be the radius of $T$ and let $v_0$ be a vertex such that the distance of each leaf of $T$ to $v_0$ is at most $d$. If we remove all leaves of $T$ at distance $d$ of $v_0$, we get a tree $T'$ with radius $d-1$. Notice that each vertex in $T'$ having a neighbor in $T-T'$ must be a leaf of $T'$. By the induction hypothesis there is an additive  coloring of $T'$ with maximum value at most $\Delta +\lceil 2\Delta /3\rceil -1$ and not using colors in $\{\lceil 2\Delta /3\rceil +1,\ldots \Delta -1\}$.

Let $v$ be a leaf of $T'$ with color $i$. When $i\le \lceil 2\Delta /3\rceil$, we color its neighbors in $T-T'$ with colors in $\{1,\ldots ,i\}\cup \{\Delta ,\ldots , \Delta +\lceil 2\Delta /3\rceil -1\}$, if $2i\ge \lceil 2\Delta /3\rceil$, and with colors in $\{i,\ldots ,\lceil 2\Delta /3\rceil \}\cup \{\Delta ,\ldots , \Delta +\lceil 2\Delta /3\rceil -1\}$, otherwise. When $i\ge \Delta$, we color its neighbors in $T-T'$ with colors in $\{\Delta ,\ldots ,i\}\cup \{1, \ldots , \lceil 2\Delta /3\rceil \}$, if $2(i-\Delta )\ge \lceil 2\Delta /3\rceil$, and with colors in $\{i,\ldots ,\Delta +\lceil 2\Delta /3\rceil -1\}\cup \{1,\ldots , \lceil 2\Delta /3\rceil \}$, otherwise. It is clear in this way we can obtain an additive coloring of $T$ which uses colors in $\Omega$. $\square$

Previous result leads us to seek an upper bound for $\chi '_a(G)$ in terms of the maximum degree in arbitrary graph. In [12] it was shown that $\chi _i(G)\le \Delta ^2-\Delta +1$ and that this upper bound is attained by the incidence graph of the projective plane of order $\Delta$ ($P_\Delta$). We prove a similar result for the additive chromatic index. We first prove that the incidence graph of $P_\Delta$ has additive chromatic index $\Delta (\Delta -1)+1$. To this purpose we shall use as the set of colors a perfect difference set $S$. It is a set of $\Delta$ integers, $s_1, \dots , s_\Delta$, having the property that their $\Delta (\Delta -1)$ differences, $s_i - s_j, i \ne j; i,j = 1, \dots \Delta$, are congruent modulo $\Delta (\Delta -1)+1$, to the integers $1,2, \dots \Delta (\Delta -1)$, in some order. In [19] it was shown that for each $\Delta -1$ which is a power of a prime number, there is a perfect difference set of size $\Delta$.

Notice that if $S$ is a perfect difference set so is the set $S'=\{s-m:s\in S\}$, where $m$ is the minimum element in $S$. Hence, we shall assume in the sequel that $0\in S$. Under this assumption it follows that for every two elements $s,s'\in S$ we have $s+s'\not \equiv 0 \mod n$, where $n=\Delta (\Delta -1)+1$. Otherwise, the two differences $0-s'$ and $s-0$ coincide modulo $n$.

For each perfect difference set $S$, with $0\in S$, and having $\Delta$ elements, we define the following representation of the incidence graph of $P_\Delta$. Let $n=\Delta (\Delta -1)+1$ and let $G(S)=(U\cup W,E(S))$ be a bipartite graph where $U$ and $W$ are copies of $[n-1]\cup \{0\}$ and $E(S)= \{xy|x \in U, y \in W; \exists s \in S : x + s \equiv y \mathrm mod n\}.$

Lemma 6

The graph $G(S)$ corresponds to the incidence graph of $P_\Delta$. Moreover, $\chi '_a(G(S))=\Delta (\Delta -1)+1$.

Proof

By its definition, the set of neighbors of a vertex $x$ in $U$ (resp. $W$) is $\{x+s\,\,\mathrm{mod}\,\, n: s\in S\}$ (resp. $\{x-s\,\, \mathrm{mod}\,\, n: s\in S\}$), where $n=\Delta (\Delta -1)+1$. Hence $G(S)$ is a $\Delta -$regular graph.

By a counting argument one can see that two vertices $x$ and $x'$ in $U$ have exactly one common neighbor in $W$, if they have at least one.

As $S$ is a perfect difference set, for each $z\equiv x-x' \mathrm{mod}\,\, n \in U$, there always exist $s$ and $s'$ such that $x-x'\equiv s'-s\, \mathrm{mod}\,\, n$. Hence, $y:=x+s\equiv x'+s$ is a common neighbor of $x$ and $x'$. A similar argument can be applied to prove that two vertices in $W$ have exactly one common neighbor in $U$. Therefore, $G(S)$ corresponds to the incidence graph of $P_\Delta$.

Moreover, previous analysis shows that $n=\chi (G^U)\le \chi '_a(G(S)).$

We prove that $\chi '_a(G(S))=n$, by showing that the coloring obtained by assigning to each vertex $i\in U\cup W$ the value $i$, is an additive coloring. It is clear that this coloring is an injective coloring as $x+s\equiv x+s' \mathrm mod n$ implies $s\equiv s'\, \mathrm{mod}\,\, n$. By the choice of $S$ this implies that $s=s'$. On the other hand, if there are $x,x'\in U$, $s,s'\in S$ such that $x+s\equiv x'+s'=:y\,\, \mathrm{mod}\,\, n$ and $x+x'\equiv 2y$, then we obtain the contradiction $s+s'\equiv 0\,\, \mathrm{mod}\,\, n$. $\square$

Our previous construction shows that the following upper bound is tight up to a constant factor.

Theorem 7

Let $G$ be a graph of maximum degree $\Delta$. Then

$$\begin{aligned} \chi '_a(G)\le 2\Delta (\Delta -1)+1. \end{aligned}$$

Proof

Our first proof of this upper bound was rather elaborate and only gives the result asymptotically. We present here a simpler proof given by B. Reed (personal communication, 2012). Let $v_1,\ldots , v_n$ be an ordering of the vertices. We construct an additive coloring greedily by following this ordering. When coloring a vertex $v_i$ we have already colored at most $\Delta (\Delta -1)$ vertices at distance two of $v_i$. Each such vertex forbids two colors to be used at vertex $v$. Hence, with $2\Delta (\Delta -1)+1$ colors this greedy strategy produces an additive coloring of $G$ with maximum value $2\Delta (\Delta -1)+1$. $\square$

3 Lower Bounds

We now show some non-trivial lower bounds for the additive chromatic index in terms of the minimum degree.

Theorem 8

Let $G=(V,E)$ be a graph with minimum degree $\delta$. Then $\chi _a'(G)\ge 5(\delta -1)/3$.

Proof

Let $\alpha :=\chi '_a(G)$, $l=:\lfloor (\alpha -\delta )/2 \rfloor +1$, and $c:=\alpha -\delta -2(l-1).$ We shall prove that $2(l-1)+c\ge (2\delta -5)/3$, and hence that $\alpha \ge 5(\delta -1)/3$.

Let $\varphi$ be an additive coloring of $G$, with $\varphi :V\rightarrow [\alpha ]$. Let $u$ be a vertex such that $\varphi (u)<\delta$. Then, at most one color between $\varphi (u)-a$ and $\varphi (u)+a$ can be used to color the neighbors of $u$, for each $a=0,\ldots ,\varphi (u)-1$. Hence, at least $\delta -\varphi (u)$ colors in $\{2\varphi (u),\ldots ,\alpha \}$ are needed to color the neighbors of $u$. This gives $\varphi (u)\le \alpha -\delta +1$. Given the definition of $c$ and $l$, we have that the set of colors that can be used to color the neighbors of $u$ is contained in

$$\begin{aligned} \{1,\ldots ,2l-1+c\}\cup \{\delta ,\ldots , \delta +2(l-1)+c\}. \end{aligned}$$

We define four parameters $\theta ^-,\theta ^+, \rho ^-, \rho ^+$ as follows.

$$\begin{aligned} \theta ^-&:= \min \{l+c-\varphi (u): \varphi (u)\le l+c\}, \\ \theta ^+&:= \min \{\varphi (u)-l-c: l+c\le \varphi (u)\le 2l-1+c\},\\ \rho ^-&:= \min \{\delta -1+l+c-\varphi (u): \delta \le \varphi (u)\le \delta -1+l+c\},\\ \rho ^+&:= \min \{\varphi (u)-l-c-\delta +1: \delta -1+l+c\le \varphi (u)\le \delta -1+2l-1+c\}. \end{aligned}$$

Let $u$ be a vertex such that $\varphi (u)=l+c-\theta ^-$. Then, the neighbors of $u$ can use at most $l+c-\theta ^-$ colors in $\{1,\ldots ,2(l+c-\theta ^-)-1\}$, at most $2\theta ^--c$ colors in $\{2(l+c-\theta ^-),\ldots ,2l+c-1\}$, and at most $2l+c-(\rho ^-+\rho ^+)$ in $\{\delta ,\ldots ,\delta +2(l-1)+c\}$. Hence, at most

$$\begin{aligned} 3l+c+\theta ^--\rho ^--\rho ^+ \end{aligned}$$

(3)

in total.

By considering a vertex $u$ such that $\varphi (u)=l+c+\theta ^+$, we deduce that there are at most

$$\begin{aligned} 3l+2c+\theta ^+-\rho ^--\rho ^+ \end{aligned}$$

(4)

colors available to color the neighbors of $u$.

Similarly, for a vertex $u$ with $\varphi (u)=\delta -1+l+c-\rho ^-$, there are at most

$$\begin{aligned} 3l+c+\rho ^--\theta ^+-\theta ^- \end{aligned}$$

(5)

colors that can be used to color the neighbors of $u$.

Finally, for a vertex with $\varphi (u)=\delta -1+l+c+\rho ^+$, there are no more than

$$\begin{aligned} 3l+2c+\rho ^+-\theta ^+-\theta ^--2 \end{aligned}$$

(6)

colors for coloring the neighbors of $u$.

By adding Eqs. (3), (4), (5), and (6), we get

$$\begin{aligned} 12l+6c-\theta ^--\theta ^+-\rho ^--\rho ^+-2\ge 4\delta , \end{aligned}$$

which implies

$$\begin{aligned} 2(l-1)+c\ge (2\delta -5)/3. \end{aligned}$$

$\square$

When we apply the bound obtained above to $\Delta$-regular graphs we get the following result.

Corollary 9

Let $G=(V,E)$ be a $\Delta$-regular graph. Then $\chi _a'(G)\ge 5(\Delta -1)/3$.

4 Computational Complexity of Computing $\chi '_a(G)$

We have seen so far that additive colorings are injective colorings with additional constraints on the color allowed in the neighborhood of each vertex. A similar restriction applies to $L(p,q)$-labeling, a related concept introduced in [11]. A vertex coloring $c$ of a graph $G$ with colors in $[k]\cup \{0\}$ such that $|c(u)-c(v)|\ge p$ when $u$ and $v$ are adjacent and $|c(u)-c(v)|\ge q$ when they are at distance two in $G$ is called a $L(p,q)$-labeling of $G$. Let $\lambda (p,q)(G)$ be the smallest integer $k$ such that there is a $L(p,q)$-labeling with colors in $[k-1]\cup \{0\}$. From the computational complexity point of view it is known that for each $p\ge q$, such that $q$ does not divide $p$, and for each integer $k$, to decide whether $\lambda _{p,q}(G)\le k$ is NP-hard, even when restricted to trees [9]. On the other hand, it is shown in [4] that $\lambda _{2,1}(G)$ can be computed in polynomial time on trees. More recently, a linear time algorithm for computing $\lambda _{2,1}(G)$ for trees was proved in [16]. The method presented in [4] can be extended to compute $\lambda _{p,1}(G)$ in polynomial time.

Here we show how a similar idea can be used to compute the additive chromatic index of trees. For a tree of maximum degree $\Delta$, we can reduce the computation of its additive chromatic index to the problem of deciding whether it has an additive coloring with maximum value $l$, for each value $l\in \{\Delta ,\ldots , 5\Delta /3\}$.

We present the result in a slightly more general framework which includes previous notions. Let us consider injective colorings with colors in a given set $\mathcal {C}$. We associate to each color $a\in \mathcal {C}$ a graph $H_a=(C_a,R_a)$, where $C_a$ is a subset of $\mathcal {C}$. The role of the graph $H_a=(C_a,R_a)$ is to express additional constraints to injective colorings. On the one hand, if a vertex $u$ gets color $a$, then $C_a$ indicates the colors that can appear in $N_G(u)$. On the other hand, an edge $cc'$ in $R_a$ indicates that $c$ and $c'$ can not be both in $N_G(u)$.

Let $T=(V,E)$ be a tree and $c:V\rightarrow \mathcal {C}$ an injective coloring. We say that $c$ is feasible for $(H_a)_{a\in \mathcal {C}}$ if for each vertex $u\in V$, the set $c(N_T(u))$ is an independent set in the graph $H_{c(u)}$.

Let $\mathcal {C}=[k]$, for some positive integer $k$ and for each $a\in [k]$, let $H_a=([k],\emptyset )$. In this situation, a feasible injective coloring is just an injective coloring using colors in $[k]$. On the other hand, given positive integers $p,q$, $p\ge q$, if for each $a\in [k]\cup \{0\}$ the graph $H_a$ has vertex set $([k]\cup \{0\}){\setminus } \{a-p+1,\ldots ,a+p-1\}$ and edge set $\{ij: i,j\in [k]\cup \{0\}, i\ne j, |i-j|<q\}$, then a feasible injective coloring is, in fact, a $L(p,q)$-labeling. Finally, if for each $a\in [k]$, the vertex set of $H_a$ is $[k]$ and its edge set is $\{ij:i+j=2a\}$, then we have that a feasible injective coloring is an additive coloring. We notice that each family $(H_a)_{a\in \mathcal {C}}$ previously associated to injective colorings, additive colorings or $L(p,1)$-labelings satisfies the following property: for each $a\in \mathcal {C}$, each connected component of $H_a$ is a complete graph. In fact, in these situations each connected component is either an isolated vertex or consists of two adjacent vertices.

In order to determine the existence of feasible injective coloring we use the natural extension of the dynamic programming algorithm given in [4] to our framework.

Given a leaf $r$ of $T$ and a vertex $u\ne r$, we denote by $T^u$ the subtree of $T$ which contains the neighbor of $u$ in the path in $T$ between $r$ and $u$, which we call the father of $u$ in $T$, and every vertex $v$ such that the path in $T$ between $v$ and $r$ contains $u$. By instance if $u$ is the neighbor of $r$ in $T$, then $r$ is the father of $u$ and $T^u=T$. Let $N'_T(u)$ denote the set $N_T(u){\setminus } \{f(u)\}$ which is the set of all neighbors of $u$ in the tree $T$ excluding its father.

For each vertex $u$ and each color $a\in {\mathcal C}$ we say color $b\in C_a$ is compatible with $u$ and $a$, if $T^u$ has a feasible injective coloring $c$ such that $c(f(u))=a$ and $c(u)=b$. Let $C(u,a)$ denote the set of colors which are compatible with $u$ and $a$. It is clear that if there are colors $a$ and $b$ such that $b\in C(u,a)$, where $u$ is the (unique) neighbor of $r$ in $T$, then $T^u=T$ has a feasible injective coloring.

The following dynamic programming algorithm computes the compatible sets for given $T$, $C$ and a given family $(H_a)_{a\in \mathcal {C}}$. We present the algorithm for any collection $(H_a)_{a\in \mathcal {C}}$, although only for special families we can guarantee that it runs in polynomial time.

Compatible Sets

Input: A tree $T=(V,E)$ and $r$ a leaf of $T$; a set of color ${\mathcal C}$ and a family of graphs $(H_a=(C_a,R_a))_{a\in {\mathcal C}}$, where $C_a\subseteq \mathcal {C}$, for each $a\in \mathcal {C}$.

Output: For each vertex $u$, $u\ne r$, and each color $a\in {\mathcal C}$, the set of compatible colors $C(u,a)$.

• 1. For each leaf $u$, $u\ne r$, for each color $a$, set $C(u,a)=C_a$; mark vertex $u$ as processed.

• 2. Iteratively, take a vertex $u$ in $T$, $u\ne r$, not yet processed and such that for every vertex in $N'_T(u)$ all compatible sets have been determined. For each color $a$, compute $C(u,a)$ using the following equivalence: $b\in C(u,a)$ if and only if for each $v\in N'_T(u)$ there exists a color $d_v \in C(v,b)$, such that the set $\{d_v: v\in N'_T(u)\}\cup \{a\}$ is an independent set of $H_b$. At the end, mark vertex $u$ as processed and continue with unprocessed vertices.

This strategy can be implemented in time $O(n|{\mathcal C}|^2K)$, where $K$ is the time needed to determine whether $b\in C(u,a)$, for a given vertex $u$, and given colors $a$ and $b$.

When for each $a\in \mathcal {C}$, each connected component of the graph $H_a$ is a complete graph, a feasible injective coloring $c$ of $T$ must assign to each vertex $v\in N_T(u)$ a color in a different connected component of $H_{c(u)}$. In this situation, given colors $a$ and $b$ and a vertex $u$, the problem of determining whether $b\in C(u,a)$ can be formulated as a maximum matching problem in the auxiliary bipartite graph $G=(N'_T(u)\cup B,E)$, where $B$ is the set of connected components of $H_b$ which do not contain color $a$ and $vs\in E$ whenever $v\in N'_T(u)$, $s\in B$ and $V(s)\cap C(v,b)\ne \emptyset$, where $V(s)$ is the set of colors in $s$.

We have that $T^u$ admits a feasible injective coloring $c$ with $c(u)=b$ and $c(f(u))=a$ if and only if $G$ has a matching $M$ such that $N'_T(u)$ is contained in the set $V(M):=\{v:\exists e\in M, v\in e\}$. In fact, if $G$ has a matching $M$ with $N'_T(u)\subseteq V(M)$, then for each $v\in N'_T(u)$ there is a connected component $s$ of $H_b$ such that $C(v,b)\cap V(s)\ne \emptyset$. Hence, for each $v\in N'_T(u)$, the subtree $T^v$ has a feasible injective coloring such that $c_v(v)\in V(s)$ and $c_v(u)=b$. These feasible injective colorings can be extended to an injective coloring $c$ of $T^u$ by defining $c(w)=c_v(w)$ for each $w\in T^v$ and $c(f(u))=a$. As each $c(v)$ belongs to a different connected component of $H_b$, the set $\{c(v):v\in N'_T(u)\}\cup \{a\}$ is an independent set of $H_b$. Therefore, $c$ is a feasible injective coloring of $T^u$. Conversely, if $T^u$ has a feasible injective coloring $c$, then $c$ must assign to each vertex in $N'_T(u)$ a color in a different connected component of $H_b$. As $c(f(u))=a$, no color in the connected component of $H_b$ containing $a$ can be used to color vertices in $N'_T(u)$. Moreover, for every two distinct vertices $v$ and $w$ in $N'_T(u)$, $c(v)$ and $c(w)$ belong to different connected components in $H_b$. Then, $M:=\{vs: c(v)\in V(s)\in B\}$ is a matching of $G$ such that $N'_T(u)$ is contained in $V(M)$.

The time needed to compute a maximum matching in a bipartite graph whose independent sets are of size $|N(u)|-1\le \Delta$ and $|C_a|\le |{\mathcal C}|$ is $O(\Delta ^{1.5}|{\mathcal C}|)$.

Theorem 10

In time $O(\Delta ^{1.5} n|{\mathcal C}|^3)$ we can decide whether a tree with $n$ vertices and of maximum degree $\Delta$ admits a feasible injective coloring for $(H_a)_{a\in {\mathcal C}}$, when for each $a\in \mathcal {C}$, each connected component of $H_a$ is a complete graph.

From Theorem 10 applied to the family $(H_a)_{a\in \mathcal {C}}$ associated to additive colorings we get that in time $O(\Delta ^{1.5} nl^3)$ we can decide whether a tree $T$ with $n$ vertices and of maximum degree $\Delta$ admits an additive coloring with colors in $[l]$. From Proposition 5 we get the following corollary.

Corollary 11

The additive chromatic index can be computed in time $O(\Delta ^{4.5}n \log \Delta )$ in a tree with $n$ vertices and of maximum degree $\Delta$.

We now consider the computation of the additive chromatic index in larger classes of graphs. A natural class to consider is the class of bounded treewidth graphs. For this class it is known that any decision problem admitting a Monadic Second Order Logic formula has a polynomial time algorithm [5]. Let $k$-Additive Coloring  denote the problem of deciding whether a graph $G$ has additive chromatic index at most $k$. For each fixed $k$, we have the following.

Lemma 12

The problem $k$-Additive Coloring can be expressed by a Monadic Second Order Logic formula of size only depending on $k$.

Proof

In the following formula, the sets $X_1,\ldots ,X_k$ will correspond to the color sets, and the three vertices $x,y,z$ to any path of length $2$. Part (8) of the formula states that vertices $x,y,z$ receive colors in $[k]$, part (9) states that vertices $x$ and $z$ receive different colors, and part (10) states that the colors given to vertices $x,y,z$ do not form an arithmetic progression.

$$\begin{aligned}&\displaystyle \exists X_1,\ldots ,X_k \subseteq V(G) \mathrm s.t. \forall x,y,z \in V(G) : \big (\{x,y\} \in E(G) \wedge \{y,z\} \in E(G)\big ) \Rightarrow \nonumber \\ \end{aligned}$$

(7)

$$\begin{aligned}&\displaystyle \Big [\big ( \bigvee _{i \in [k]} x \in X_i \big ) \wedge \big (\bigvee _{i \in [k]} y \in X_i\big ) \wedge \big (\bigvee _{i \in [k]} z \in X_r\big )\Big ] \end{aligned}$$

(8)

$$\begin{aligned}&\displaystyle \wedge \lnot \Big [\bigvee _{i \in [k]} \big (x \in X_i \wedge z \in X_i\big )\Big ] \end{aligned}$$

(9)

$$\begin{aligned}&\displaystyle \wedge \lnot \Big [\bigvee _{i,j \in [k]} \big (x \in X_i \wedge y \in X_{i+j} \wedge z \in X_{i+2j}\big )\Big ] \end{aligned}$$

(10)

$\square$

From the result in [5] we immediately get the following.

Theorem 13

The problem $k$-Additive Coloring, for any fixed $k$, has a polynomial time algorithm when restricted to classes of graphs of bounded treewidth.

We do not know whether the problem remains polynomially solvable when $k$ is part of the input, even for serie-parallel graphs, i.e. graphs of treewidth at most two. On the other hand, we prove that the problem is hard for $k=4$, even when restricted to 3-regular graphs. To this end we show that $4$-Additive Coloring  reduces the problem of deciding whether a graph has a proper 3-edge coloring. This latter problem was proved to be NP-complete in [15], even when restricted to 3-regular graphs.

Theorem 14

The problem $k$-Additive Coloring, for $k=4$, is NP-complete, even when restricted to 3-regular graphs.

Proof

To see that $k$-Additive Coloring belongs to NP, we notice that the additive chromatic index is monotone under subgraphs. Hence an upper bound for its value on the complete graph $K_n$ is an upper bound for its value in any graph on $n$ vertices. As the right hand side of Eq. 1 is $O(n^2)$, an additive coloring for a graph on $n$ vertices has a description of length polynomial in $n$. This shows that the problem belongs to NP.

In order to prove the statement, for each 3-regular graph $G$ we build a 3-regular graph $G'$ such that $G$ is 3-edge-colorable if and only if $G'$ has an additive coloring with colors in $\{1,a,4\}$, with $a=2$ or $a=3$.

The vertex set of graph $G'$ has two vertices $(uv)_u$ and $(uv)_v$, for each edge $e=uv$ of $G$. Two vertices $x$ and $y$ of $G'$ are adjacent if and only if there is an edge $uv$ with $x=(uv)_u$ and $y=(uv)_v$ or there are two edges $uv$ and $uw$ in $G$ with $x=(uv)_u$ and $y=(uw)_u$. Then each vertex $x=(uv)_u$ of $G'$ has three neighbors: $(uv)_v$, $(uw)_u$ and $(uz)_u$, where $v,w,z$ are the neighbors of vertex $u$ in $G$. Hence $G'$ is 3-regular and it is clear that it can be constructed in polynomial time.

Any proper edge coloring of $G$ with three colors can be transformed in an additive coloring of $G'$ which uses colors in the set $\{1,2,4\}$ as follows. In $G'$ we assign color $i$ to the two vertices $e_u$ and $e_v$ associated to an edge $e$ of $G$ with color $i$, for $i=1,2$, and color $4$ when $e$ has color $3$. Hence, if the edges $uv$, $uw$ and $uz$, incident to vertex $u$, have colors 1, 2 and 3, respectively, then $(uv)_u=(uv)_v=1$, $(uw)_u=(uw)_w=2$ and $(uz)_u=(uz)_z=4$. Hence, we get an additive coloring of $G'$.

Conversely, an additive coloring with colors in $\{1,2,3,4\}$ uses either colors $1,2,4$ or $1,3,4$ in each set $A(u):=\{(uv)_u,(uw)_u,(uz)_u\}$ because $A(u)$ induces a complete graph, for each vertex $u$. Therefore, colors $1$ and $4$ are used in each set $A(u)$. Moreover, if $a$ is the neighbor of a vertex $b\in A(u)$ not in $A(u)$, then it has the same color as $b$. This allows us to color each edge $uv$ in $G$ with color $1$ (resp. 3), when its associated vertices $(uv)_u$ and $(uv)_v$ are colored with color 1 (resp. 4) in $G'$. The remaining edges are colored with color 2. $\square$

In view of previous results it is interesting to consider whether we can approximate the additive chromatic number in polynomial time. We can use Theorem 2 to obtain (in)approximability results for the additive chromatic index based on previous results obtained for the injective chromatic number. In [14], it was proved that there is a polynomial time approximation algorithm for $\chi _i(G)$ with an approximation factor $n^{1/3}$ when restricted to split graphs. Moreover, they proved that this result is tight in the following sense. They showed that unless $\mathsf ZPP =\mathsf NP$, for each $\epsilon >0$ there is no polynomial time approximation algorithm for $\chi _i(G)$ with a factor $n^{1/3-\epsilon }$, even for the class of split graphs. This result was based on an inapproximability result for the chromatic number obtained in [8]. From a result obtained in [21], we now know that the condition $\mathsf ZPP =\mathsf NP$ can be strengthened to $\mathsf P =\mathsf NP$.

Let us assume that there are $\epsilon >0$ and a polynomial time approximation algorithm which on input $G$ computes an approximation $\alpha$ for the additive chromatic index laying between $\chi '_a(G)$ and $n^{1/3-\epsilon }\chi '_a(G)$.

From Theorem 2 we have that there is a constant $c$ such that $\chi '_a(G)\le \chi _i(G)g(\chi _i(G)$, where $g(x)=c2^{\sqrt{2\log (x)}}$ is a non negative, non decreasing function, and for each $\epsilon >0$, $g(n)\le n^{\epsilon /2}$, for $n$ large enough. Then, for each $\epsilon >0$ we have

$$\begin{aligned} \chi _i(G)\le \alpha \le n^{1/3-\epsilon }\chi _i(G) g(n)\le n^{1/3-\epsilon /2}\chi _i(G), \end{aligned}$$

for each graph $G$ with $n$ vertices, and $n$ large enough. This implies the following result.

Theorem 15

For each $\epsilon >0$, unless $\mathsf P =\mathsf NP$, there is no polynomial time approximation algorithm with approximation factor $n^{1/3-\epsilon }$ for the additive chromatic index, even when restricted to split graphs.

On the other hand, if for a graph $G$ on $n$ vertices we can compute in polynomial time a value $v$ such that $\chi _i(G)\le v \le \chi _i(G) n^{1/3}$, then we can use $vg(v)$ to get an approximated value for $\chi '_a(G)$. In fact, we know from Theorem 2 that $\chi '_a(G)\le \chi _i(G) g(\chi _i(G))$. Hence $\chi '_a(G)\le vg(v)$, as $xg(x)$ is a non-decreasing function.

Applying the function $xg(x)$ to $\chi _i(G) n^{1/3}$ we get $\chi _i(G) n^{1/3} g(\chi _i(G) n^{1/3})$. But, $g( \chi _i(G)n^{1/3} ) \le g(n^{4/3})$ and for each value $\epsilon >0$, $g(n^{4/3})$ is smaller than $n^{\epsilon }$, for $n$ large enough. Therefore, for $n$ large enough we have

$$\begin{aligned} \chi '_a(G)\le vg(v) \le \chi '_a(G) n^{1/3+\epsilon }. \end{aligned}$$

As we previously mentioned, in [14], it was proved that there is a polynomial time approximation algorithm for $\chi _i(G)$ with an approximation factor $n^{1/3}$ when restricted to split graphs. Hence, our previous analysis immediately implies the following result.

Theorem 16

For each $\epsilon >0$, there is a polynomial time approximation algorithm with approximation factor $n^{1/3+\epsilon }$ for the additive chromatic index, when restricted to split graphs.

It is clear that based upon Theorem 3 we can obtain similar approximation results between the additive chromatic index and the injective chromatic number for bipartite graphs. This linear relation between these two parameters makes interesting the following result.

Theorem 17

For each fixed $k\ge 3$, the problem of deciding whether an input graph has injective chromatic number at most $k$, is NP-complete, even restricted to bipartite graphs of maximum degree $k$.

Proof

Let $G=(V,E)$ be a $k$-regular graph and let $I(G)$ be the incident graph of $G$ defined as the bipartite graph with independent sets $V$ and $E$ such that $ve$ is an edge of $I(G)$, whenever $e$ is incident with $v$ in $G$. Notice that if $G$ has maximum degree $k$, then so has $I(G)$.

It is not hard to see that for the incidence graph $I(G)$, it holds that $(I(G))^V$ is the original graph $G$ and that $(I(G))^E$ is the line graph of $G$. Therefore, from Eq. 2 we get

$$\begin{aligned} \chi _i(I(G))=\max \{\chi (G),\chi '(G)\}. \end{aligned}$$

From Brooks’ Theorem ([3]) we get that $\chi _i(I(G))=\chi '(G)$, unless $G$ is a complete graph. Therefore, computing the injective chromatic number of $I(G)$, a bipartite graph of maximum degree $k$, is as hard as computing the chromatic index of $G$, a $k$-regular graph. As it is known that computing the chromatic index of $k$ regular graphs is NP-hard we obtain the statement of the theorem. $\square$

5 Conclusion

We have seen that computing the additive chromatic number on complete graphs as well as in balanced complete bipartite graphs depends on non-trivial additive properties of integers. We think that it is worth to consider the problem in others classes of well structured graphs as products of paths and/or cycles, balanced complete 3-partite graphs, and more generally, balanced complete $k$-partite graphs. We think that this study may require more sophisticated additive combinatorics tools in order to obtain lower bounds.