# On $\lambda$-backbone coloring of cliques with tree backbones in linear time

Krzysztof Michalik<EMAIL_ADDRESS>Krzysztof Turowski111Krzysztof
Turowski’s work was supported by Polish National Science Center
$2020$/$39$/D/ST$6$/$00419$ grant<EMAIL_ADDRESS>Department of Theoretical Computer Science,
Faculty of Mathematics and Computer Science,
Jagiellonian University, Łojasiewicza $6$, Kraków, Poland

###### Abstract

A $\lambda$-backbone coloring of a graph $G$ with its subgraph (also called a
_backbone_) $H$ is a function $c\colon V(G)\rightarrow\\{1,\dots,k\\}$
ensuring that $c$ is a proper coloring of $G$ and for each $\\{u,v\\}\in E(H)$
it holds that $|c(u)-c(v)|\geq\lambda$.

In this paper we propose a way to color cliques with tree and forest backbones
in linear time that the largest color does not exceed
$\max\\{n,2\lambda\\}+\Delta(H)^{2}\lceil\log{n}\rceil$. This result improves
on the previously existing approximation algorithms as it is
$(\Delta(H)^{2}\lceil\log{n}\rceil)$-absolutely approximate, i.e. with an
additive error over the optimum.

We also present an infinite family of trees $T$ with $\Delta(T)=3$ for which
the coloring of cliques with backbones $T$ require to use at least
$\max\\{n,2\lambda\\}+\Omega(\log{n})$ colors for $\lambda$ close to
$\frac{n}{2}$.

###### keywords:

graph coloring , backbone coloring , complete graphs , trees , approximation
algorithms

††journal: Discrete Mathematics

##  1 Introduction

Within the general framework of graph coloring problems there exists an
important class of problems that is related to the frequency assignment
problem: for a given set of transmitters (which are represented by the
vertices of a graph) and their adjacency (i.e. adjacent transmitters are close
enough or have strong enough signal), assign the frequency bands to the
transmitters in a way that keeps interference below a defined level while
minimizing total frequency span. In some applications it makes sense to
distinguish a certain substructure of the network (called the _backbone_),
designed as the most important part for the communication, so it has to meet
additional restrictions on the assignment.

This leads us to the backbone coloring problem, introduced by Broersma in [3].
First, let us define formally the backbone coloring, using a standard graph
notation, e.g. from [2]:

######  Definition 1.

Let $G$ be a graph and $H$ be a subgraph of $G$ with $V(G)=V(H)$. Let also
$\lambda\in\mathbb{N}_{+}$, $\lambda\geq 2$. The _$\lambda$ -backbone
coloring_ of $G$ with backbone $H$ is defined as a function $c\colon
V(G)\to\mathbb{N}_{+}$ such that

  * •

$c(u)\neq c(v)$ for every $uv\in E(G)$,

  * •

$|c(u)-c(v)|\geq\lambda$ for every $uv\in E(H)$.

Note that it differs from the vertex coloring problem in important ways: in an
optimal $\lambda$-backbone coloring (i.e. using a minimum number of colors)
the ordering of the colors matters, therefore we might observe that some
smaller colors are not used while the larger ones are in use.

Broersma et. al. in [3] also defined the backbone coloring problem as an
extension of a classical vertex coloring problem:

######  Definition 2.

Let $G$ be a graph and $H$ be a subgraph of $G$ with $V(G)=V(H)$. Let also
$\lambda$ be a natural number greater than $1$. The _$\lambda$ -backbone
coloring problem_ is defined as following: for a given $k$ does there exists
$c\colon V(G)\to[1,k]$ such that $c$ is a $\lambda$-backbone coloring of $G$
with backbone $H$.

The _$\lambda$ -backbone coloring number_ for a graph $G$ with backbone $H$
(denoted as $BBC_{\lambda}(G,H)$) is then defined as the smallest $k$ such
that there exists a $\lambda$-backbone coloring of $G$ with backbone $H$.

Note that here and throughout the whole paper we rely on the notation $[a,b]$
representing a set of integers between $a$ and $b$, inclusive.

In general, it is straightforward to prove that the problem of determining
$BBC_{\lambda}(G,H)$ is $\mathcal{NP}$-hard [3]. In the same paper which
introduced this problem there were shown basic bounds on the value of the
$\lambda$-backbone coloring number, depending on $\chi(G)$, the chromatic
number of $G$:

######  Theorem 3 (Broersma et al., [3]).

Let $G$ be a graph and $H$ its subgraph. Then $\chi(G)\leq
BBC_{\lambda}(G,H)\leq\lambda(\chi(G)-1)+1$.

In [6] and [7] there were proposed other bounds, suited particularly for
graphs with $\chi(H)\ll\chi(G)$:

######  Theorem 4 (Havet et al., [6]).

Let $G$ be a graph and $H$ its subgraph. Then
$BBC_{\lambda}(G,H)\leq(\lambda+\chi(G)-2)\chi(H)-\lambda+2$.

######  Theorem 5 (Janczewski, Turowski, [7]).

Let $G$ be a graph on $n$ vertices and $H$ its subgraph. Then
$\lambda(\chi(H)-1)+1\leq
BBC_{\lambda}(G,H)\leq\lambda(\chi(H)-1)+n-\chi(H)+1$.

The $\lambda$-backbone coloring problem was studies for several classes of
graphs, for example split graphs [4], planar graphs [6], complete graphs [8],
and for several classes of backbones: matchings and disjoint stars [4],
bipartite graphs [8] and forests [6]. For a special case $\lambda=2$ it was
also studies for may other cases e.g. triangle-free graphs with tree backbones
[10], outerplanar graphs with matching backbones [1] and general graphs with
bounded degree backbones [11] or with tree and path backbones [3].

In this paper, we turn our attention to the special case when the graph is
complete (denoted $K_{n}$) and its backbone is a (nonempty) tree or a forest
(which we will denote by $T$ and $F$, respectively). Note that it has a
natural interpretation as a labeling problem: how to assign different labels
to all vertices such that on every backbone edge the difference between labels
is at least $\lambda$. This description draws a comparison e.g. to
$L(k,1)$-labeling problem (see e.g. [5] for a survey), where the colors of any
two adjacent vertices have to differ by at least $k$ and the colors of any two
vertices within distance $2$ have to be distinct.

In our case it is obvious that $\chi(K_{n})=n$, $\chi(F)=2$ and the theorems
presented above combined together give us the following bounds:

$\displaystyle\max\\{n,\lambda+1\\}\leq
BBC_{\lambda}(K_{n},F)\leq\lambda+n-1.$

Moreover, it was proved before in [7] that there exists a $2$-approximate
algorithm for complete graphs with bipartite backbones and a $3/2$-approximate
algorithm for complete graphs with connected bipartite backbones. Both
algorithms run in linear time. As a corollary, it was proved that we can
compute $BBC_{\lambda}(K_{n},F)$ in quadratic time, provided that $F$ is a
tree on $n$ vertices and $\lambda>n-2$. On the other hand, for $\lambda=2$ we
know that $BBC_{\lambda}(K_{n},F)\leq n+1$ and we can solve the problem in
polynomial time [13, Theorem 3]. However, this leaves us with the large gap
for the intermediate values of $\lambda$, which we try to address in this
paper.

We start Section 2 by proving that if $F$ is a tree or forest on $n$ vertices
with a maximum degree $\Delta(F)$, then
$BBC_{\lambda}(K_{n},F)\leq\max\\{n,2\lambda\\}+\Delta^{2}(F)\lceil\log{n}\rceil$.
Note that this bound can be much better than the previously known ones,
especially for $\lambda$ close to $\frac{n}{2}$ and small $\Delta(F)$. We also
provide a polynomial (linear for trees, quadratic for forests) algorithm to
find the respective $\lambda$-backbone coloring.

This, in turn, combined with another much simpler algorithm allows us to show
that we can find in polynomial time a $\lambda$-backbone coloring for $G$ with
backbone forest $F$ that uses at most $\Delta^{2}(F)\lceil\log{n}\rceil$
colors more than the optimal algorithm.

Previously it was known that $BBC_{\lambda}(K_{n},T)=\lambda+n-1$ when $T$ is
a star. However, one can ask a more general question: how large can
$BBC_{\lambda}(K_{n},T)$ be when $\Delta(T)$ is small. In Section 3 we show
that there exists a family of trees with $\Delta(T)=3$ such that
$BBC_{\lambda}(K_{n},T)\geq\max\\{n,2\lambda\\}+\frac{1}{48}\log_{\phi}{n}-3$.
This result is complementary to the one in the previous section, as it shows
that sometimes we need up to $\max\\{n,2\lambda\\}+\Theta(\log{n})$ colors
even when we have $\Delta(T)=3$. In a sense, we might also say that the
logarithmic loss over a trivial lower bound
$BBC_{\lambda}(K_{n},T)\geq\max\\{n,\lambda+1\\}$ for backbone coloring of
$K_{n}$ with a tree backbone $T$ is tight.

Finally, Section 4 concludes with a presentation of some open problems related
to our work.

##  2 Complete graph with tree or forest backbone: an algorithm

In this section we will proceed as following: we first introduce so-called
red-blue-yellow $(k,l)$-decomposition of a forest $F$ on $n$ vertices, which
finds a small set $Y$ (of size $l$) such that we can split $V(F)\setminus Y$
into two independent and almost equal sets $R$, $B$ (with $|R|-|B|\leq k$).
Then, we show that we can color $R$ and $B$ with sets of consecutive colors
and assign to vertices from $Y$ the smallest and the largest colors in a way
that in total we find a $\lambda$-backbone coloring in which the maximum color
does not exceed $\max\\{n,2\lambda\\}$ more than $\Delta^{2}(F)\log{n}$.

We start with a few remarks on notation and some definitions. Let $c$ be a
unique $2$-coloring (up to the permutations of colors) of a tree $T$. Let us
also define $C_{i}(T)=\\{v\in V(T)\colon c(v)=i\\}$, i.e. the number of
vertices in color $i$, for $i=1,2$. Assume without loss of generality that $c$
is such that $C_{i}(T)$ form a non-increasing sequence.

Throughout the paper we will use a concept of tree imbalance, defined formally
as:

######  Definition 6.

Let $T$ be a tree and $c$ its $2$-coloring with properties described above. We
define the _imbalance number_ $imb(T)$ as the difference $C_{1}(T)-C_{2}(T)$.

From this definition it directly follows that $imb(T)\geq 0$.

######  Lemma 7.

In every tree $T$ there exists a vertex $v\in V(T)$ such that every connected
component of $T-v$ has at most $\frac{|V(T)|}{2}$ vertices. Such vertex can be
found in $O(|V(T)|)$ time.

###### Proof.

By rooting a tree in any vertex and traversing it recursively a constant
number of times we can compute in $O(|V(T)|)$ time the number of vertices in
each subtree of every vertex. Therefore, we assume in the analysis that these
values are already available at each vertex.

We will now describe the procedure of walking along the tree. For any vertex
$v_{i}$ let us assume that it is the current root of $T$ and let us denote its
children with their subtrees by $v_{i,j}$ and $T_{i,j}$, respectively. If for
every child $v_{i,j}\in N(v_{i})$ we have $|V(T_{i,j})|\leq\frac{|V(T)|}{2}$,
then we found our vertex. Otherwise, let us pick as $v_{i+1}$ a vertex
$v_{i,j^{\prime}}$ such that $|V(T_{i,j^{\prime}})|>\frac{|V(T)|}{2}$. Note
that it is unique among the neighbors of $v_{i}$.

If it holds that $|V(T_{i,j^{\prime}})|>\frac{|V(T)|}{2}$ we reduce the size
of the maximum subtree by at least one, i.e. we ensure that
$\max_{j}|V(T_{i+1,j})|\leq|V(T_{i,j^{\prime}})|-1=\max_{j}|V(T_{i,j})|-1$.
Observe that every $T_{i+1,j}$ but one (rooted in $v_{i}$) is a subtree of
$T_{i,j^{\prime}}-v_{i,j^{\prime}}$. Therefore, the sizes of all these trees
cannot exceed $|V(T_{i,j^{\prime}})|-1$. And the size of the last subtree of
$T_{i,j^{\prime}}-v_{i,j^{\prime}}$, rooted in $v_{i}$, has size equal to
$|V(T)|-|V(T_{i,j^{\prime}})|$, which is smaller than $|V(T_{i,j^{\prime}})|$
due to the assumption that $|V(T_{i,j^{\prime}})|>\frac{|V(T)|}{2}$.

Therefore, if we start from any $v_{0}\in V(T)$, then after at most
$\frac{|V(T)|}{2}$ steps we will find $v_{i}$ with desired properties. ∎

######  Definition 8.

Let $T$ be a tree on $n$ vertices. Let also $k$ be an integer. We call a
partition $(R,B,Y)$ such that $V(T)=R\cup B\cup Y$ a _red-blue-yellow_
$(k,l)$-decomposition if $|Y|\leq l$ and $R$ and $B$ are independent sets with
$|R|-|B|=k$.

From this definition it follows that if $(R,B,Y)$ is a _red-blue-yellow_
$(k,l)$-decomposition, then $(B,R,Y)$ is a _red-blue-yellow_
$(-k,l)$-decomposition.

######  Lemma 9.

For a tree $T$ and any $k\in[0,imb(T)]$ there exists a red-blue-yellow
$(k,\lceil\log{n}\rceil)$-decomposition.

###### Proof.

First, let us attach a set $D$ of $k$ isolated vertices to the tree $T$, thus
obtaining a forest $T^{*}$.

Now, we will describe an iterative procedure that will preserve certain
invariants, which guarantee the convergence to a solution. We let $T_{0}=T$,
$R_{0}=D$, $B_{0}=Y_{0}=\emptyset$. The invariants, which are preserved during
every step of the algorithms are:

  1. 1.

$V(T^{*})=R_{i}\cup B_{i}\cup Y_{i}\cup V(T_{i})$,

  2. 2.

$T_{i}$ is a tree,

  3. 3.

$R_{i}$ and $B_{i}$ are independent sets,

  4. 4.

$T_{i}$ does not have neighbors in $R_{i}\cup B_{i}$,

  5. 5.

$0\leq|R_{i}|-|B_{i}|\leq imb(T_{i})$,

Of course all of them hold for $i=0$.

We will define $R_{i+1}$, $B_{i+1}$, $Y_{i+1}$, $T_{i+1}$ iteratively using a
following procedure: first, we use Lemma 7 on $T_{i}$ and get $v$ of some
degree $d$ with its $d$ subtrees $T^{\prime}_{j}$ such that
$|V(T^{\prime}_{j})|\leq\frac{|V(T_{i})|}{2}$ for every $j\in[1,d]$. Without
loss of generality we assume that $T^{\prime}_{j}$ are sorted non-decreasingly
by their imbalance number.

If at any point of the algorithm it holds that
$|R_{i}|-|B_{i}|>\sum_{j=1}^{d}imb(T^{\prime}_{j})$, then it has to be the
case that $|R_{i}|-|B_{i}|>imb(T_{i})-1$. But from the invariant (5) we know
that $|R_{i}|-|B_{i}|\leq imb(T_{i})$, so it is true that
$|R_{i}|-|B_{i}|=imb(T_{i})$. Then, we observe that the partition made by $R$
and $B$ as, respectively, the larger and the smaller of the sets $R_{i}\cup
C_{2}(T_{i})\setminus D$, $B_{i}\cup C_{1}(T_{i})\setminus D$ together with
$Y=Y_{i}$ meets all the requirements of a red-blue-yellow $k$-decomposition of
$T$.

Therefore, from now on we assume that at each step it holds
$|R_{i}|-|B_{i}|\leq\sum_{j=1}^{d}imb(T^{\prime}_{j})$. Observe that
$\sum_{j=1}^{d}imb(T^{\prime}_{j})\geq imb(T_{i})-1$, as in the worst case
$v\in C_{1}(T_{i})$ and all subtrees of $v$ have at least as many vertices
from $C_{1}(T_{i})$ as from $C_{2}(T_{i})$ (i.e. $imb(T_{i})$ comes a sum of
their imbalances and we do not subtract any element).

We define $T_{i+1}=T^{\prime}_{d}$ (i.e. the subtree with the largest
imbalance) and $Y_{i+1}=Y_{i}\cup\\{v\\}$. Now we define $R_{i}(0)=R_{i}$,
$B_{i}(0)=B_{i}$ and we proceed iteratively for $j=0,1,2,\ldots,d-2$. At each
step we let $R_{i}(j+1)$ and $B_{i}(j+1)$ be, respectively, the larger and the
smaller from the sets $R_{i}(j)\cup C_{2}(T^{\prime}_{j})$ and $B_{i}(j)\cup
C_{1}(T_{j})$. In other words, we create a union of the larger set $R$ and the
small partition of $T^{\prime}_{j}$, and another union of the smaller set $B$
and the large partition of $T^{\prime}_{j}$. Finally, we let
$R_{i+1}=R_{i}(d-1)$ and $B_{i+1}=B_{i}(d-1)$.

The crucial observation is that after $j$-th iteration we have

$\displaystyle|R_{i}(j)|-|B_{i}(j)|\leq\sum_{j^{\prime}=j+1}^{d}imb(T^{\prime}_{j^{\prime}}).$

Clearly this holds for $j=0$ as it is identical to
$|R_{i}|-|B_{i}|\leq\sum_{j=1}^{d}imb(T^{\prime}_{j})$. To prove it
inductively for $j=1,2,\ldots,d-1$, we distinguish two cases:

  * •

if $|R_{i}(j-1)|-|B_{i}(j-1)|<imb(T^{\prime}_{d})$, then

$\displaystyle|R_{i}(j)|-|B_{i}(j)|$
$\displaystyle=\left||R_{i}(j-1)|+|C_{2}(T^{\prime}_{j})|-|B_{i}(j-1)|-|C_{1}(T^{\prime}_{j})|\right|$
$\displaystyle=\left||R_{i}(j-1)|-|B_{i}(j-1)|-imb(T^{\prime}_{j})\right|$
$\displaystyle\leq\max\\{|R_{i}(j-1)|-|B_{i}(j-1)|,imb(T^{\prime}_{j})\\}\leq
imb(T^{\prime}_{d}),$

  * •

if $|R_{i}(j-1)|-|B_{i}(j-1)|\geq imb(T^{\prime}_{d})$, then

$\displaystyle|R_{i}(j)|-|B_{i}(j)|$
$\displaystyle=|R_{i}(j-1)|+|C_{2}(T^{\prime}_{j})|-|B_{i}(j-1)|-|C_{1}(T^{\prime}_{j})|$
$\displaystyle=|R_{i}(j-1)|-|B_{i}(j-1)|-imb(T^{\prime}_{j})$
$\displaystyle\leq\sum_{j^{\prime}=j}^{d}imb(T^{\prime}_{j^{\prime}})-imb(T^{\prime}_{j})=\sum_{j^{\prime}=j+1}^{d}imb(T^{\prime}_{j^{\prime}}),$

where the second to last inequality follows from the induction assumption that
$|R_{i}(j-1)|-|B_{i}(j-1)|\leq\sum_{j^{\prime}=j}^{d}imb(T^{\prime}_{j^{\prime}})$.

Therefore, we directly obtain that
$|R_{i+1}|-|B_{i+1}|\leq\sum_{j^{\prime}=j+1}^{d}imb(T^{\prime}_{j^{\prime}})$
– which proves that the invariant (5) holds also for $i+1$.

The invariants (1) and (3) for $i+1$ are clearly met from the construction of
$R_{i+1}$, $B_{i+1}$, $Y_{i+1}$ and $T_{i+1}$. Similarly, invariant (4) for
$i+1$ follows from the fact that $T_{i+1}$ is adjacent to $v$ and no other
vertex from $V(T_{i})\setminus V(T_{i+1})$. And by the invariant (4) for $i$,
$T_{i}$ has its neighbors only in $Y_{i}$. Thus, $T_{i+1}$ has only neighbors
from $Y_{i}$ or $v$ itself.

Moreover, from invariant (4) for $i$ we know that if $u_{1}\in R_{i}$ and
$u_{2}\in T_{i}$, then $u_{1}u_{2}\notin E(T)$. Moreover, all sets
$C_{l}(T^{\prime}_{j})$ are independent and for any $w_{1}\in T^{\prime}_{j}$
and $w_{2}\in T^{\prime}_{j^{\prime}}$ with $j\neq j^{\prime}$ we have
$w_{1}w_{2}\notin E(T)$. All these facts guarantee that $R_{i+1}$ is also an
independent set. Finally, we can provide an identical reasoning for $B_{i+1}$
– which completes the proof of invariant (2) for $i+1$.

For the above construction, aside from the invariants, it also holds that
$|Y_{i+i}|=|Y_{i}|+1$ and $|V(T_{i+1})|\leq\frac{1}{2}|V(T_{i})|$. Thus, after
$t\leq\lceil\log{n}\rceil$ iterations we get $0\leq
imb(T_{t})\leq|V(T_{t})|=0$, and therefore $|R_{t}|=|B_{t}|$, while
$|Y_{t}|\leq\lceil\log{n}\rceil$. It is easy to check that $R_{t}\setminus D$,
$B_{t}\setminus D$ and $Y_{t}$ form a red-blue-yellow
$(k,\lceil\log{n}\rceil)$-decomposition of $T$.

Finally, the running time of the whole procedure is linear: every step $i$ can
be done in time proportional to the number of vertices in $T_{i}$, and at
every step we decrease the remaining tree size by half. ∎

######  Lemma 10.

For a forest $F=\bigcup_{i=1}^{r}T_{i}$ on $n$ vertices consisting of $r$
trees and any $k\in[0,\sum_{i=1}^{r}imb(T_{i})]$ there exists a red-blue-
yellow $(k,\lceil\log{n}\rceil)$-decomposition of $F$.

###### Proof.

Assume that $T_{i}$ are sorted nondecreasingly by $imb(T_{i})$. The main idea
of the proof is as follows: we split the vertices of the first $r-1$ trees
into two sets. Finally, we show that it is sufficient to partition only the
vertices of $T_{r}$ using Lemma 9 to find a red-blue-yellow decomposition for
the whole forest.

We again start by adding a set $D$ of $k$ isolated to the forest to form
$F^{*}$. We start with $R_{0}=D$, $B_{0}=\emptyset$, $F_{0}=F$.

For $i=1,2,\ldots,r-1$ we proceed as following: let $F_{i}=F_{i-1}\setminus
T_{i}$ and $R_{i}$, $B_{i}$ be the larger and the smaller from the sets
$R_{i-1}\cup C_{2}(T_{i})$ and $B_{i-1}\cup C_{1}(T_{i})$, respectively.

Similarly as before, it is sufficient to prove that at each point of the
algorithm it holds that

$\displaystyle 0\leq|R_{i}|-|B_{i}|\leq\sum_{j=i+1}^{r}imb(T_{j}).$

This clearly holds for $i=0$. Assume now it does hold for all $j<i$ for some
$i=1,2,\ldots,r-1$. Then, we have to distinguish two cases:

  * •

either it holds that $|R_{i-1}|-|B_{i-1}|\leq imb(T_{r})$, so directly from
the construction we get

$\displaystyle|R_{i}|-|B_{i}|$
$\displaystyle\leq\left||R_{i-1}|+|C_{2}(T_{i})|-|B_{i-1}|-|C_{1}(T_{i})|\right|$
$\displaystyle=\left||R_{i-1}|-|B_{i-1}|-imb(T_{i})\right|$
$\displaystyle\leq\max\\{|R_{i-1}|-|B_{i-1}|,imb(T_{i})\\}\leq imb(T_{r}),$

  * •

or it is true that $|R_{i-1}|-|B_{i-1}|>imb(T_{r})$, so

$\displaystyle|R_{i}|-|B_{i}|$
$\displaystyle=|R_{i-1}|+|C_{2}(T_{i})|-|B_{i-1}|-|C_{1}(T_{i})|$
$\displaystyle=|R_{i-1}|-|B_{i-1}|-imb(T_{i})$
$\displaystyle\leq\sum_{j=i}^{r}imb(T_{j})-imb(T_{i})\leq\sum_{j=i+1}^{r}imb(T_{j}).$

Either way, the invariant holds also for $i$. Therefore, it holds also for
$i=r-1$.

Finally, let $k^{\prime}=|R_{r-1}|-|B_{r-1}|$ and observe that $F_{r}=T_{r}$
is a tree and $0\leq k^{\prime}\leq imb(T_{r})$, so we can apply Lemma 9 to
obtain $(R^{\prime},B^{\prime},Y^{\prime})$ as its red-blue-yellow
$(k^{\prime},\lceil\log{n}\rceil)$-decomposition. Then, we can denote by $R$
and $B$ the larger and the smaller of the sets $R_{r-1}\cup
R^{\prime}\setminus D$ and $B_{r-1}\cup B^{\prime}\setminus D$ – and easily
verify that $(R,B,Y)$ is a red-blue-yellow
$(k,\lceil\log{n}\rceil)$-decomposition for $F$. ∎

In order to formulate our results for the $\lambda$-backbone coloring problem,
we need a simple lemma, which enables us to color a clique with a forest
backbone with a given set of colors:

######  Lemma 11.

Let $F$ be a forest on $n$ vertices with a partition $V(F)=A\cup B$ into
disjoint independent sets $A$ and $B$. Let also $[a_{1},a_{2}]$ and
$[b_{1},b_{2}]$ be intervals such that $a_{2}-a_{1}>|A|$, $b_{2}-b_{1}>|B|$,
$a_{1}+\lambda\leq b_{1}$ and $a_{2}+\lambda\leq b_{2}$.

Then, there exists a $\lambda$-backbone coloring $c$ of $K_{n}$ with backbone
$F$ such that $c(v)\in[a_{1},a_{2}]$ for every $v\in A$ and
$c(v)\in[b_{1},b_{2}]$ for every $v\in B$. Moreover, this coloring can be
found in $O(n)$ time.

###### Proof.

If $F$ contains only isolated vertices, then we can assign in any order colors
from $[a_{1},a_{2}]$ to $A$ and from $[b_{1},b_{2}]$ to $B$, as it clearly
would be a required $\lambda$-backbone coloring.

If $F$ has a leaf $v\in B$ with a neighbor $u\in A$, then we can assign
$c(v)=b_{1}$, $c(u)=a_{1}$ and invoke a subproblem for
$F^{\prime}=F-\\{u,v\\}$, $A^{\prime}=A\setminus\\{u\\}$,
$B^{\prime}=B\setminus\\{v\\}$ with color intervals $[a_{1}+1,a_{2}]$ and
$[b_{1}+1,b_{2}]$. The complete solution would be valid, as all other
neighbors of $u$ in $F$ would get colors at least
$b_{1}+1\geq\lambda+a_{1}+1>\lambda+c(u)$.

Similarly, if $F$ has a leaf $v\in A$ with a neighbor $u\in B$, then we can
assign $c(v)=a_{2}$, $c(u)=b_{2}$ and invoke the same subproblem as above,
only this time with color intervals $[a_{1},a_{2}-1]$ and $[b_{1},b_{2}-1]$.
Again it is easy to check that after obtaining a solution for a subproblem all
constraints for $u$ and $v$ will also be satisfied. ∎

Interestingly, the lemma above can be applied to the $\lambda$-backbone
coloring problem directly. Note that here we can extend the notation $C_{1}$,
$C_{2}$ used before for trees – only this time we admit that it is relative to
a $2$-coloring $c$, which in case of forests may not be unique:

######  Theorem 12.

Let $F$ be a forest on $n$ vertices and a $c$ be its $2$-coloring such that
$|C_{1}(F)|\geq|C_{2}(F)|$, where $C_{i}(F)=\\{v\in V(F)\colon c(v)=i\\}$. It
holds that $BBC_{\lambda}(K_{n},F)\leq\max\\{\lambda+|C_{1}(F)|,n\\}$.
Moreover, we can find a respective coloring in $O(n)$ time.

###### Proof.

Let $L=\max\\{\lambda,C_{2}(F)\\}$. Let also $A=C_{2}(F)$, $B=C_{1}(F)$ with
$[a_{1},a_{2}]=[1,|C_{2}(F)|]$ and $[b_{1},b_{2}]=[L+1,L+|C_{1}(F)|$. It is
easy to verify that these choices meet the conditions of Lemma 11, so we
directly infer that there exists a $\lambda$-backbone coloring $c$ using only
colors no greater than $L+|C_{1}(F)|$. ∎

More surprisingly, we can couple Lemma 11 with a red-blue-yellow decomposition
to obtain slightly different bound:

######  Theorem 13.

For a forest $F$ on $n$ vertices it holds that
$BBC_{\lambda}(K_{n},F)\leq\max\\{n,2\lambda\\}+\Delta^{2}(F)\lceil\log{n}\rceil$.
Moreover, we can find a respective coloring in $O(n)$ time.

###### Proof.

Let $L=\max\left\\{\frac{n}{2},\lambda\right\\}$. From Lemma 10 we can get a
red-blue-yellow $(0,\lceil\log{n}\rceil)$-decomposition $(R,B,Y)$ of $F$. Note
that by construction it holds that $|R|=|B|\leq L$.

Observe that $Y$ is not necessarily an independent set. Therefore, we need to
guarantee the correctness of the coloring for the edges with both endpoints in
$Y$. We handle that in the following way: we obtain $F^{\prime}$ from $F$ by
contracting all edges with both endpoints in $R\cup B$. From a $2$-coloring
$c^{\prime}$ of $F^{\prime}$ we construct a partition of $Y=Y_{1}\cup Y_{2}$
such that both $Y_{i}=\\{v\in Y\colon c^{\prime}(v)=i\\}$. Without loss of
generality assume that $|Y_{1}|\geq|Y_{2}|$.

Let $\mathcal{N}_{G}(U)$ be a set of neighbors of vertices from $U$ in $G$,
i.e.

$\displaystyle\mathcal{N}_{G}(U)=\\{v\in V(G)\colon\exists_{u\in
U}\\{u,v\\}\in E(G)\\}$

Denote now by $B_{1}=B\cap\mathcal{N}_{F}(Y_{1})$ and
$R_{1}=R\cap\mathcal{N}_{F}(B_{1})$. Let also
$R_{2}=R\cap\mathcal{N}_{F}(Y_{2})$, $B_{2}=B\cap\mathcal{N}_{F}(R_{2})$ and
$B^{*}=B\setminus(B_{1}\cup B_{2})$, $R^{*}=R\setminus(R_{1}\cup R_{2})$. Note
that by this construction $B_{1}\cap B_{2}=R_{1}\cap R_{2}=\emptyset$. If this
was not the case, then it would mean that there exist a path
$(u_{1},v_{1},v_{2},u_{2})$ in $F$ such that $u_{1}\in Y_{1}$, $u_{2}\in
Y_{2}$ and $v_{1},v_{2}\in R\cup B$. However, this would mean that in
$F^{\prime}$ both $u_{1}$ and $u_{2}$ had to be assigned the same color – so
they could not be in $Y_{1}$ and $Y_{2}$, respectively.

To simplify the notation we define $D=\Delta(F)$. We will proceed with the
coloring as following:

  * •

vertices from $Y_{1}$ will get colors from $1$ to $|Y_{1}|$,

  * •

vertices from $B$ will get colors from $D|Y_{1}|+1$ to $L+D|Y_{1}|$,

  * •

vertices from $R$ will get colors from $L+D^{2}|Y_{1}|+1$ to
$2L+D^{2}|Y_{1}|$,

  * •

vertices from $Y_{2}$ will get colors from $2L+D^{2}|Y_{1}|+(D-1)|Y_{2}|+1$ to
$2L+D^{2}|Y_{1}|+D|Y_{2}|$.

. We will color $F$ by assigning colors to $Y_{1}$, $B_{1}$ and $R_{1}$ first,
and then to $Y_{2}$, $R_{2}$ and $B_{2}$, symmetrically. Finally, we prove
that we are left with the part of the set $R^{*}\cup B^{*}$ that can be
colored using the remaining colors (see Figure 1 for the assignment of colors
to the sets of vertices).

$Y_{1}$$B$$R$$Y_{2}$1$|Y_{1}|$$D|Y_{1}|+1$$D|Y_{1}|+L$$1+L+D^{2}|Y_{1}|$$2L+D^{2}|Y_{1}|$$M-|Y_{2}|+1$$M$
(a) Division into sets $R$, $B$, $Y_{1}$ and $Y_{2}$.

$Y_{1}$$B_{2}$$B^{*}$$B_{1}$$R_{2}$$R^{*}$$R_{1}$$Y_{2}$$\geq L$$\geq L$$\geq
L$$\geq L$ (b) Division of $R$ and $B$ into subsets $R$, $B$, $Y_{1}$ and
$Y_{2}$.

(c) Edges which are forced by the construction of all the subsets.

$Y_{1}$$B_{2}$$B^{*}$$B_{1}$$R_{2}$$R^{*}$$R_{1}$$Y_{2}$ (d) Other possible
connections between the subsets.

Figure 1: The main idea for the $\lambda$-backbone coloring based on a red-
blue-yellow decomposition. For brevity, $M=2L+D^{2}|Y_{1}|+D|Y_{2}|$ denotes
the maximum color used.

First, let us arrange vertices from $Y_{1}$ in any order and assign them
colors from $1$ to $|Y_{1}|$. Now, let us take vertices from $B_{1}$ and
assign them the largest colors from the set $[D|Y_{1}|+1,L+D|Y_{1}|]$ in the
following way: the vertex with the largest colored neighbor in $Y_{1}$ gets
$L+D|Y_{1}|$, second largest gets $L+D|Y_{1}|-1$ etc. (ties are broken
arbitrarily). Such a coloring ensures two things: first, all color constraints
between $Y_{1}$ and $B_{1}$ are met, and second, the smallest color used for
$B_{1}$ is at least $L+1$.

Similarly, we color $R_{1}$: we sort the vertices according to the largest
colors of their neighbors in $B_{1}$ and assign the largest colors to the ones
with the largest neighbor color. Thus we are certain that all color
constraints between $B_{1}$ and $R_{1}$ are met and that the smallest color
used for $R_{1}$ is at least $2L+D|Y_{1}|+1$, since every vertex from $B_{1}$
has at most $D-1$ neighbors in $R_{1}$.

It is easy to verify that in the same fashion we can color $Y_{2}$, $R_{2}$,
and $B_{2}$, only this time starting from assigning the smallest colors
available for each set (see Figure 1).

Since there are at most $L$ vertices in both $R$ and $B$, we are sure that the
sets of colors assigned to $B_{1}$ and $B_{2}$ (or $R_{1}$ and $R_{2}$,
respectively) do not overlap. Furthermore, by construction, there only remain
to be colored the vertices from the set $R^{*}\cup B^{*}$. Note that any $v\in
B^{*}$ can be adjacent only to some $u\in Y_{2}\cup R_{1}$ (or to $u\in
R^{*}$) – but the largest color to be used for $B^{*}$ (certainly at most the
largest color for $B$, i.e. $L+D|Y_{1}|$) is at least lower by $L$ from the
smallest color used in $Y_{2}\cup R_{1}$ (i.e.
$2L+D^{2}|Y_{1}|-D(D-1)|Y_{1}|=2L+D|Y_{1}|$). Again, the symmetrical argument
goes for $R^{*}$ and $Y_{1}\cup B_{2}$.

By the argument above, the remaining colors for $B^{*}$ and $R^{*}$ form
intervals $[b_{1},b_{2}]$ and $[r_{1},r_{2}]$ such that $b_{1}+L\leq r_{1}$,
$b_{2}+L\leq r_{2}$. Thus, we are in position to color $F[R^{*}\cup B^{*}]$
with its disjoint independent sets $R^{*}$, $B^{*}$ and colors
$[b_{1},b_{2}]$, $[r_{1},r_{2}]$ using Lemma 11. ∎

######  Theorem 14.

There exists an algorithm with running time $O(n)$ which for any tree $T$ on
$n$ vertices finds a $\lambda$-backbone coloring such that
$BBC_{\lambda}(K_{n},T)\leq OPT+\Delta^{2}(T)\lceil\log{n}\rceil$.

###### Proof.

We proceed as following: we run the algorithms from Theorem 12 and Theorem 13
and we return the better result. It guarantees that

$\displaystyle BBC_{\lambda}(K_{n},T)$
$\displaystyle\leq\min\\{\max\\{\lambda+|C_{1}(T)|,n\\},\max\\{n,2\lambda\\}+\Delta^{2}(T)\lceil\log{n}\rceil\\}$
$\displaystyle\leq\max\\{\min\\{\lambda+|C_{1}(T)|,2\lambda\\},n\\}+\Delta^{2}(T)\lceil\log{n}\rceil.$

Clearly, the $\lambda$-backbone coloring obtained from Theorem 12 is always
feasible – and it is the best among all $\lambda$-backbone colorings $c$ such
that $\lceil\frac{c}{\lambda}\rceil$ is a $2$-coloring of $T$.

Moreover, in all other $\lambda$-backbone colorings $c$ we have to use at
least one color greater than $2\lambda$ – as $\lceil\frac{c}{\lambda}\rceil$
has to be a valid coloring of $T$, but it has to use more than $2$ colors – so
$\max_{v\in V(T)}c(v)\geq 2\lambda+1$.

Therefore, it is true that
$BBC_{\lambda}(K_{n},T)\geq\min\\{\lambda+|C_{1}(T)|,2\lambda+1\\}$. And of
course we have to use a different color for each vertex, so
$BBC_{\lambda}(K_{n},T)\geq n$.

Combining all these bounds we obtain the desired result. ∎

To achieve the same result for forest backbones we only need to add some edges
that would make the backbone connected and spanning. However, it is clear that
we can always attach them to the leaves of the trees in the forest and we will
not increase the maximum degree of the forest.

######  Corollary 15.

There exists an algorithm with running time $O(n)$ which for any forest $F$ on
$n$ vertices with $\Delta(F)\geq 2$ finds a $\lambda$-backbone coloring such
that $BBC_{\lambda}(K_{n},F)\leq OPT+\Delta^{2}(F)\lceil\log{n}\rceil$.

##  3 Complete graph with tree or forest backbone: a lower bound

In this section we prove that there exists a family of trees with the maximum
degree $3$ for which
$BBC_{\lambda}(K_{n},T)\geq\max\\{n,2\lambda\\}+\Theta(\log{n})$ in four
steps. First, we will define the family of trees with parameters directly
related to the Fibonacci numbers. Next, we will show that the existence of a
red-blue-yellow $(k,l)$-decomposition for such trees implies the existence of
another red-blue-yellow $(k^{\prime},l)$-decomposition with an additional
property. Then, we will prove that any such decomposition would imply further
that there holds a certain decomposition of some large number (i.e. half of
the large Fibonacci number) into a sum and a difference of a small number of
Fibonacci numbers. Finally, we will establish that such decomposition cannot
exist – therefore there is no red-blue-yellow $(k,l)$-decomposition for our
trees assuming that $k$ and $l$ are proportional to $\log{n}$.

We begin by tying our $(k,l)$-red-blue-yellow decomposition to the backbone
coloring problem:

######  Theorem 16.

Let $T$ be a tree on $n$ vertices. Let also $\lambda\geq 2$ and $l$ be any
positive integers such that $2\lambda+l\geq n$. If $T$ does not have a red-
blue-yellow $(k,l)$-decomposition for any
$k\in[0,\min\\{\lambda-1,2\lambda-n+l\\}]$, then
$BBC_{\lambda}(K_{n},T)>2\lambda+l$.

###### Proof.

Suppose that $T$ is a tree that does not have any red-blue-yellow
decomposition for any $k\in[0,\min\\{\lambda-1,2\lambda-n+l\\}]$, but at the
same time it is true that $BBC_{\lambda}(K_{n},T)\leq 2\lambda+l$ with some
optimal $\lambda$-backbone coloring $c$.

Now we can define the following sets:

  * •

$R^{\prime}=\\{v\in V(T)\colon 1\leq c(v)\leq\lambda\\}$,

  * •

$B^{\prime}=\\{v\in V(T)\colon\lambda+1\leq c(v)\leq 2\lambda\\}$,

  * •

$Y=\\{v\in V(T)\colon c(v)>2\lambda\\}$.

Since all vertices in $c$ have different colors, it is true that $|Y|\leq l$.
Moreover, let $R$ and $B$ be the larger and the smaller from the sets
$R^{\prime}$ and $B^{\prime}$, respectively.

By the definition of the backbone coloring, $R$ and $B$ have to be independent
sets in $T$ with $k^{\prime}=|R|-|B|\leq\lambda-1$.

On the other hand, we know that $R$ has to contain at most $\lambda$ vertices
and $B$ has to contain at least $n-\lambda-|Y|$ vertices, so
$k^{\prime}\leq\lambda-(n-\lambda-|Y|)\leq 2\lambda-n+l$. Thus, $(R,B,Y)$ is a
red-blue-yellow $(k^{\prime},l)$-decomposition of $T$ with
$k^{\prime}\in[0,\min\\{\lambda-1,2\lambda-n+l\\}]$—and we obtained a
contradiction. ∎

Now we define a family of _Fibonacci trees_ , built recursively:

######  Definition 17.

We call a rooted tree the $N$-th Fibonacci tree (denoted as $T^{F}_{N}$) if:

  * •

$T^{F}_{1}=T^{F}_{2}=K_{1}$,

  * •

$T^{F}_{N}$ for $N\geq 3$ is a tree with root $u_{1}$ with only child $u_{2}$
such that $u_{2}$ has two subtrees, which are, respectively, $(N-1)$-th and
$(N-2)$-th Fibonacci trees.

We will ultimately show that this class contains infinitely many trees
(starting from certain $N_{0}$), presented in Figure 2, cannot be colored
using less than $\max\\{n,2\lambda\\}+\frac{1}{48}\log_{\phi}{n}-3$ colors.

(a) $T^{F}_{1}$, $T^{F}_{2}$

(b) $T^{F}_{3}$

(c) $T^{F}_{4}$

(d) $T^{F}_{5}$

Figure 2: Fibonacci trees for $N=1,2,3,4,5$. White vertices are the roots of
Fibonacci trees and gray vertices are the roots of their Fibonacci subtrees.

We will additionally denote by $T^{F}_{N}$ the $N$-th (unrooted) Fibonacci
tree an unrooted version of the $N$-th rooted Fibonacci tree. In our analysis
we will only be using rooted Fibonacci trees, but all the results apply also
to the unrooted variant as we can recognize Fibonacci trees and find their
roots in $O(|V(T)|)$ time.

Here we will also make use of $C_{1}(T^{F}_{N})$ and $C_{2}(T^{F}_{N})$ sets.
Without a loss of generality from now on we always define these sets with
respect to a $2$-coloring $c$ of $T^{F}_{N}$ such that the root of $T^{F}_{N}$
has color $1$.

######  Fact 18.

For every $N$ each vertex of $T^{F}_{N}$ is either the root or the parent of
the root of some $T^{F}_{i}$ subtree for some $i\in[0,N]$.

######  Theorem 19.

If $T^{F}_{N}$ is the $N$-th Fibonacci tree, then $|V(T^{F}_{N})|=3F_{N}-2$,
where $F_{N}$ is the $N$-th Fibonacci number.

Moreover, for $n\geq 10$ it holds that $N=\lfloor\log_{\phi}{n}\rfloor$.

###### Proof.

The first part of the theorem obviously holds for $N=1,2$. If we assume that
the theorem holds for all $i\in[0,N-1]$ for some $N\geq 3$, then

$\displaystyle|V(T^{F}_{N})|$
$\displaystyle=|V(T^{F}_{N-1})|+|V(T^{F}_{N-2})|+2=3F_{N-1}-2+3F_{N-2}-2+2$
$\displaystyle=3F_{N}-2.$

The second part of the theorem we prove as follows: $n=3F_{N}-2$ implies that
$\frac{\sqrt{5}}{3}(n+2)=\phi^{N}-(-\phi)^{-N}$. Therefore, we know that for
$n\geq 2$ ($N\geq 3$) it holds that

$\displaystyle\log_{\phi}\left(\phi^{N}-(-\phi)^{-N}\right)\geq
N+\log_{\phi}\left(1-\phi^{-2N}\right)\geq
N-\frac{\phi^{-2N}}{\ln{\phi}}-\frac{\phi^{-4N}}{\ln{\phi}}>N-\frac{1}{5},$

where we used the fact that $\ln(1-x)\geq-x-x^{2}$ for $x\in(0,0.68)$.

On the other hand,

$\displaystyle\log_{\phi}\left(\phi^{N}-(-\phi)^{-N}\right)\leq
N+\log_{\phi}\left(1+\phi^{-2N}\right)\leq
N+\frac{\phi^{-2N}}{\ln{\phi}}+\frac{\phi^{-4N}}{\ln{\phi}}<N+\frac{1}{5},$

where we used the fact that $\ln(1+x)\leq x+x^{2}$ for all $x>0$.

Finally, for $n\geq 10$ ($N\geq 5$) it holds that

$\displaystyle\log_{\phi}\left(\frac{\sqrt{5}}{3}(n+2)\right)$
$\displaystyle=\log_{\phi}{n}+\log_{\phi}\left(\frac{\sqrt{5}}{3}\right)+\log_{\phi}\left(1+\frac{2}{n}\right)$
$\displaystyle\leq\log_{\phi}{n}-\frac{3}{5}+\frac{2}{n\log{\phi}}+\frac{4}{n^{2}\log{\phi}}<\log_{\phi}{n}-\frac{1}{5},$

and
$\log_{\phi}\left(\frac{\sqrt{5}}{3}(n+2)\right)>\log_{\phi}{n}+\log_{\phi}\left(\frac{\sqrt{5}}{3}\right)>\log_{\phi}{n}-\frac{4}{5}$.

By putting all these bounds together we obtain that $N<\log_{\phi}{n}<N+1$,
which completes the proof. ∎

######  Theorem 20.

If $T^{F}_{N}$ is the $N$-th Fibonacci tree, then $imb(T^{F}_{N})=F_{N}$,
where $F_{N}$ is $N$-th Fibonacci number.

###### Proof.

Clearly $imb(T^{F}_{N})=F_{N}$ for $N=1,2$.

Let $N\geq 3$ and proceed by induction. By construction, we know that the
grandchildren of the root of $T^{F}_{N}$ are exactly the roots of
$T^{F}_{N-1}$ and $T^{F}_{N-2}$ and they all have the same color in any
$2$-coloring of $T^{F}_{N}$. Therefore,

$\displaystyle imb(T^{F}_{N})$
$\displaystyle=imb(T^{F}_{N-1})+imb(T^{F}_{N-2})=F_{N-1}+F_{N-2}=F_{N}.$

∎

Observe that the set of vertices which are the roots of all Fibonacci subtrees
is defined exactly by $C_{1}(T^{F}_{N})$. Using 18 we can modify any
$(k,l)$-red-blue-yellow decomposition in such a way that $Y\cap
C_{1}(T^{F}_{N})=\emptyset$:

######  Lemma 21.

Let $(R,B,Y)$ be a red-blue-yellow $(k,l)$-decomposition of a Fibonacci tree
$T^{F}_{N}$. Then there exists $0\leq k^{\prime}\leq k+2l$ such that we can
construct a red-blue-yellow $(k^{\prime},l)$-decomposition
$(R^{\prime},B^{\prime},Y^{\prime})$ of $T^{F}_{N}$ with $Y^{\prime}\cap
C_{1}(T^{F}_{N})=\emptyset$.

###### Proof.

First, we define $Y^{\prime}=\\{v\in C_{2}(T^{F}_{N})\colon v\in Y\lor
parent(v)\in Y\\}$, i.e. we “push down” the yellow color from roots of
Fibonacci subtrees to their children. Clearly, $|Y^{\prime}|\leq|Y|$.

Next, we define $R^{\prime}$ and $B^{\prime}$ to be as following:

  * •

if $v\in C_{2}(T^{F}_{N})$, $v\notin Y$ and $parent(v)\notin Y$, then we
preserve the color: if $v\in R$, then put $v$ in $R^{\prime}$, otherwise put
it in $B^{\prime}$,

  * •

if $v\in C_{1}(T^{F}_{N})$ and $v\notin Y$, then we also preserve the color,

  * •

if $v\in C_{1}(T^{F}_{N})$, $v\in Y$ and $parent(v)\notin Y$, then we use the
color other than in the parent: if $parent(v)\in R$, then put $v$ in
$B^{\prime}$, otherwise put $v$ in $R^{\prime}$,

  * •

finally, if $v\in C_{1}(T^{F}_{N})$, $v\in Y$ and $parent(v)\in Y$, we put $v$
in $R^{\prime}$.

Overall, this whole procedure “extends” blue and red parts to the previously
yellow vertices on a single level just below them. And if we are certain that
both a parent and an only child of a vertex in $C_{1}(T^{F}_{N})$ will be in
$Y^{\prime}$ (the last case above), then we just assign it to $R^{\prime}$, as
it will be surrounded only by the vertices from $Y^{\prime}$ (in fact, it can
be also added to $B^{\prime}$ instead).

Note that $|R^{\prime}|\leq|R|+|Y|$ as only in the last two cases we can add
some vertices to $R^{\prime}$ which were not in $R$ – but this means that
these vertices were in $Y$. Additionally,
$|B^{\prime}|\geq|B|-|Y^{\prime}|\geq|B|-|Y|$, as the only vertices which are
in $B\setminus B^{\prime}$ are exactly the ones which are added to
$Y^{\prime}$.

Finally, it is easy to verify that indeed $(R^{\prime},B^{\prime},Y^{\prime})$
is a red-blue-yellow $(k^{\prime},l)$-decomposition of $T^{F}_{N}$ for some

$\displaystyle|k^{\prime}|=||R^{\prime}|-|B^{\prime}||\leq||R|-|B|+2|Y||\leq
k+2l.$

Although $k^{\prime}$ in the equation above might be negative, remember that
we can always make it positive by swapping $R^{\prime}$ and $B^{\prime}$. ∎

Now, we turn to the computation of the imbalances of red-blue parts of
Fibonacci trees. In order to do that, we have to recall some theory of
Fibonacci numbers. In particular, we recall the Zeckendorf’s theorem [9],
which states that any number $n\in\mathbb{N}$ can be written as
$n=\sum_{j}z_{j}F_{j}$ for $z_{j}\in\\{0,1\\}$ such that

  1. (A)

no two consecutive $z_{j}$ are equal to $1$, i.e. $z_{j}z_{j+1}=0$ for all
$j$,

  2. (B)

this representation is unique and it is the shortest decomposition with
respect to $\sum_{j}|z_{j}|$,

  3. (C)

it can be constructed by greedy subtraction the largest possible Fibonacci
numbers from $n$ until we reach $0$.

We call a vector $z=(z_{j})_{j=1}^{\infty}$ such that $(A)$ – and thus also
$(B)$ and $(C)$ – holds the _Zeckendorf representation_ of $n$ and denote by
$Z(n)$. We will sometimes without loss of generality trim $Z(n)$ to a finite
number of positions since $F_{i}>n$ implies trivially $z_{i}=0$.

For example, $Z(F_{N})=(0,\ldots,0,1)$, i.e. it has a single one on $N$-th
position and $Z\left(\frac{F_{N}}{2}\right)=(\ldots,1,0,0,1,0,0)$, i.e. it has
ones only on every third position ending at $N-2$ as it is true that
$\frac{F_{N}}{2}=F_{N-2}+\frac{F_{N-3}}{2}$.

Now we may proceed to the lemma which ties tree decompositions and Fibonacci
numbers:

######  Lemma 22.

For any red-blue-yellow $(k,l)$-decomposition $(R,B,Y)$ of $T^{F}_{N}$ such
that $Y\cap C_{1}(T^{F}_{N})=\emptyset$ and $k\geq 0$ it holds that every
connected component $T_{i}$ of $T^{F}_{N}[R\cup B]$ has

$\displaystyle imb(T_{i})=|Y_{i}|+F_{r}-\sum_{j=1}^{N}z_{j}F_{j}$

where $r\in[1,N]$, $Y_{i}=\\{v\in Y\colon parent(v)\in V(T_{i})\\}$,
$z_{j}\in\\{0,1\\}$ for all $j=1,2,\ldots,N$ and
$\sum_{j=1}^{N}z_{j}\leq|Y_{i}|$.

###### Proof.

Each component $T_{i}$ of $T^{F}_{N}[R\cup B]$ is a tree rooted in a vertex
$u_{i}$ that is also a root of some Fibonacci subtree. It may be a Fibonacci
subtree itself – but even if it is not, then it means it has some subtrees
removed, which are cut off exactly in vertices from $Y_{i}$. But every $v\in
Y_{i}$ has children that are also roots of some Fibonacci subtrees.

Now, let us define $c$ as a $2$-coloring of $T^{F}_{N}$ and $c_{i}$ as a
$2$-coloring of $T_{i}$, both with respective roots assigned color $1$. In
particular note that $C_{1}(T^{F}_{N})$ and $C_{2}(T^{F}_{N})$ are defined
with respect to $c$.

Observe that it has to be the case that $c(u_{i})=1$, since every root of a
Fibonacci subtree is in an even distance from the root of the whole Fibonacci
tree. Thus, for all $v\in V(T_{i})$ it holds that $c_{i}(v)=c(v)$.

Moreover, every leaf $v$ of $T_{i}$ also has $c_{i}(v)=1$, as either it is a
leaf of $T^{F}_{N}$ (thus $c(v)=1$), or it is a parent of some vertex from
$Y_{i}$. However, in the latter case $Y\cap C_{1}(T^{F}_{N})=\emptyset$
implies also that $c(v)=1$, as the vertices from $Y_{i}$ always get color $2$.

Finally, we note that to get $imb(T_{i})$ we have to:

  * •

add the imbalance of a Fibonacci subtree of $T^{F}_{N}$ (i.e. the one rooted
in $u_{i}$),

  * •

remove the imbalance of some Fibonacci subtrees of $T^{F}_{N}$ (i.e. the ones
rooted in children of all $v\in Y_{i}$) – note that for each vertex from
$Y_{i}$ we remove its two subtrees $T_{j-1}^{F}$ and $T_{j-2}^{F}$ with total
imbalance equal to $imb(T_{j-1}^{F})+imb(T_{j-2}^{F})=F_{j}$,

  * •

add the size of $|Y_{i}|$ – vertices from $Y_{i}$ were taken into account when
adding imbalance of the whole tree in the first case above, however they are
not in $T_{i}$. Note that their removal will increase the imbalance.

$T_{n-2}$$T_{n-3}$$T_{n-3}$$T_{n-4}$ Figure 3: An example Fibonacci tree
$T^{F}_{n}$ with $|Y_{1}|=2$ and the imbalance of the top tree
$imb(T_{1})=|Y_{1}|+F_{n}-F_{n-1}-F_{n-2}=2$.

Overall, if the imbalance of a Fibonacci subtree of $T^{F}_{N}$ rooted in
$u_{i}$ is equal to $F_{r}$ for some $r$, then we get that
$imb(T_{i})=|Y_{i}|+F_{r}-\sum_{j=1}^{r}z^{\prime}_{j}F_{j}$ for some
$z^{\prime}_{j}\in\mathbb{N}$ with
$\sum_{j=1}^{r}|z^{\prime}_{j}|\leq|Y_{i}|$.

We note that since we cut the subtrees of the tree rooted in $T^{F}_{N}$, the
last sum cannot exceed $F_{r}$. Moreover, the Zeckendorf representation
$Z\left(\sum_{j=1}^{r}z^{\prime}_{j}F_{j}\right)=(z_{j})_{j=1}^{r}$ is such
that $\sum_{j=1}^{r}|z_{j}|\leq\sum_{j=1}^{r}|z^{\prime}_{j}|\leq|Y_{i}|$. ∎

######  Lemma 23.

If there exists a red-blue-yellow $(k,l)$-decomposition $(R,B,Y)$ of
$T^{F}_{N}$ such that $|Y|=l$, $Y\cap C_{1}(T^{F}_{N})=\emptyset$, then there
exists a value $y\in[0,l]$ and a vector $z=(z_{j})_{j=1}^{N}$ with
$z_{j}\in\\{-1,0,1\\}$ and $\sum_{j=1}^{N}|z_{j}|\leq 2l+1$ such that

$\displaystyle\frac{F_{N}-k+l}{2}=y+\sum_{j=1}^{N}z_{j}F_{j}.$

###### Proof.

The required decomposition exists if and only if there exists a set $Y$ with
$l$ vertices such that we can and find for connected components $T_{i}$ of
$T_{N}^{F}\setminus Y$ certain $2$-coloring functions $c_{i}$ such that $R$,
$B$ are equal to the largest and the smallest of the sets $A_{1}$, $A_{2}$,
where $A_{j}=\bigcup_{i}\\{v\in V(T_{i})\colon c_{i}(v)=j\\}$ – and it is the
case that $|R|-|B|=k$.

From Lemma 22 we know that for every $i$ we can write
$imb(T_{i})=|Y_{i}|+\sum_{j=1}^{N}z_{i,j}F_{j}$ such that
$z_{i,j}\in\\{-1,0,1\\}$ and $\sum_{j=1}^{N}|z_{i,j}|\leq|Y_{i}|+1$. Thus,

$\displaystyle k=|R|-|B|$
$\displaystyle=\sum_{i=1}^{l+1}a_{i}\,imb(T_{i})=y+\sum_{i=1}^{l+1}\sum_{j=1}^{N}a_{i}z_{i,j}F_{j}.$

for $y=\sum_{i=1}^{l+1}a_{i}|Y_{i}|\in\left[-l,l\right]$ and some
$a_{i}\in\\{-1,1\\}$ (in particular, $a_{i}=-1$ if and only if the root of
$T_{i}$ has color $2$ in $c_{i}$). Note that by our assumptions on $Y$ we know
that $T_{N}^{F}\setminus Y$ has at most $l+1$ connected components.

Now let us invert colors in colorings $c_{i}$ for certain connected components
$T_{i}$ (i.e. replace some $c_{i}$ by $c^{\prime}_{i}=3-c_{i}$) and leave all
the others intact in order to color all the roots of $T_{i}$ with a color $1$.
Of course, then $c^{\prime}$ on the whole $T_{N}^{F}\setminus Y$ agrees with
the $2$-coloring of $T_{N}^{F}$ where the root has color $1$, so the total
imbalance induced by $c^{\prime}$ on $T_{N}^{F}\setminus Y$ is just the sum
all of the imbalances of $T_{i}$. Therefore,

$\displaystyle F_{N}+l$
$\displaystyle=imb(T_{N}^{F})+|Y|=\sum_{i=1}^{l+1}imb(T_{i})=|Y|+\sum_{i=1}^{l+1}\sum_{j=1}^{N}z_{i,j}F_{j}.$

Now, by subtracting the last two equations we obtain

$\displaystyle\frac{F_{N}-k+l}{2}=\frac{|Y|-y}{2}+\sum_{i=1}^{l+1}\sum_{j=1}^{N}a^{\prime}_{i}z_{i,j}F_{j},$

where we used the fact that $a^{\prime}_{i}=\frac{1-a_{i}}{2}\in\\{0,1\\}$ for
all $i=1,2,\ldots,l+1$.

Now again observe that
$\sum_{j=1}^{N}F_{j}\sum_{i=1}^{l+1}a^{\prime}_{i}z_{i,j}$ can be written as a
sum of Fibonacci numbers – possibly with some repetitions, i.e. each $F_{j}$
is used exactly $\sum_{i=1}^{l+1}a^{\prime}_{i}z_{i,j}$ times. The total
number of Fibonacci numbers in this sum does not exceed

$\displaystyle\sum_{i=1}^{l+1}\sum_{j=1}^{N}|a^{\prime}_{i}z_{i,j}|\leq\sum_{i=1}^{l+1}\sum_{j=1}^{N}|z_{i,j}|\leq\sum_{i=1}^{l+1}(|Y_{i}|+1)\leq|Y|+l+1=2l+1.$

Therefore, by Zeckendorf theorem there exists a vector
$z^{\prime}=(z^{\prime}_{j})_{j=1}^{N}$ with $z^{\prime}_{j}\in\\{-1,0,1\\}$
and $\sum_{j=1}^{N}|z^{\prime}_{j}|\leq 2l+1$ such that

$\displaystyle
Z\left(\sum_{i=1}^{l+1}\sum_{j=1}^{N}a^{\prime}_{i}z_{i,j}F_{j}\right)=z^{\prime}.$

This completes the proof. ∎

######  Lemma 24.

For $N\geq 96$, any $k\in[0,F_{N/2-1}]$, $l\in\left[1,\frac{N}{48}-1\right]$
there does not exist a value $y\in[0,l]$ and a vector $z=(z_{j})_{j=1}^{N}$
with $z_{j}\in\\{-1,0,1\\}$ and $\sum_{j=1}^{N}|z_{j}|\leq 2l+1$ such that

$\displaystyle\frac{F_{N}-k+l}{2}=y+\sum_{j=1}^{N}z_{j}F_{j}.$

###### Proof.

It is well known that $F_{N-2}<\frac{F_{N}}{2}<F_{N-1}$ for any $N\geq 4$.
Moreover, we can easily show by induction that

$\displaystyle\frac{F_{N}}{2}=\sum_{i=0}^{\lfloor\frac{N-2}{3}\rfloor}F_{N-2-3i}.$

From now on let us denote $K=F_{N/2-1}$ an $L=\frac{N}{48}-1$. Here we have
slightly harder task: we would like to show that any number
$S\in\left[\frac{F_{N}-K-L}{2},\frac{F_{N}+L}{2}\right]$ (since $y$ is at most
equal to $l$) cannot be represented using at most $2l+1$ Fibonacci numbers,
but this time using both addition and subtraction.

Note that we can split $Z\left(\frac{F_{N}}{2}\right)$ into a sequence of
$\lfloor\frac{N-1}{3}\rfloor$ blocks of length $3$ equal to $(0,1,0)$,
possibly with some padding at the beginning.

Let $S^{\prime}=S-\frac{F_{N}}{2}$. By assumption it holds that
$L<K=F_{N/2-1}$, so $|S^{\prime}|\leq\frac{K+L}{2}<F_{N/2-1}$ and therefore
$Z(|S^{\prime}|)$ cannot have ones on positions
$\left[\frac{N}{2}-1,N\right]$. Let us take positions
$\left[1,\frac{N}{2}-1\right]$ of $Z\left(\frac{F_{N}}{2}\right)$, equivalent
to some number $S^{\prime\prime}$ and observe that
$S^{\prime\prime}+S^{\prime}\geq 0$ – and, additionally, it also cannot have
ones on positions $\left[\frac{N}{2}-1,N\right]$. Therefore, we are certain
that $Z(S)$ has exactly the same values as $Z\left(\frac{F_{N}}{2}\right)$ on
positions from $\frac{N}{2}$ on. Which effectively means that
$Z(S)=Z\left(\frac{F_{N}}{2}+S^{\prime}\right)$ contains a sequence of
$\frac{N}{6}$ consecutive blocks $(0,1,0)$.

Suppose that $S=S_{1}-S_{2}$ such that $Z(S_{1})$ and $Z(S_{2})$ have in total
at most $2l+1$ ones. Now it is sufficient to prove that using the vector
addition of $Z(S)$ (consisting of $\frac{N}{6}$ consecutive blocks $(0,1,0)$)
and $Z(S_{2})$ (having only $2l+1$ ones) we cannot obtain a vector which has
only $2l+1$ ones. From now on we will concentrate only on this latter part of
the vectors $Z(S)$ and $Z(S_{2})$.

Let us write both $Z(S)$ and $Z(S_{2})$ as blocks of length $3$ and denote
$i$-th block of $Z(S_{2})$ (and also, by association, the respective block of
$Z(S)$) as type A if it contains some ones, and as type B otherwise. Note that
there can be at most $2l+1$ blocks of type A since $Z(S_{2})$ has at most
$2l+1$ ones.

Now consider how many blocks of type B can be influenced by a carry from
blocks of type A. We have to analyze not only forward carry, but also the
backward one, as for example, in Zeckendorf representation we have
$Z(3)=(0,0,0,1)$ but $Z(3+3)=(0,1,0,0,1)$.

The proof for the forward carry is simpler: if we have $i$-th block (with
$i>\frac{N}{2}$) of type A, which starts with a position $j$ (respective to
the number $F_{j}$), then we know that the number $S^{*}_{2}$ indicated only
by the blocks up to $i-1$ of $Z(S_{2})$ cannot exceed $F_{j}-1$ because of the
Zeckendorf representiation. Similarly, for $Z(S)$ the respective number
$S^{*}$ cannot exceed $F_{j-1}-1$ since its $(i-1)$-th block is already equal
to $(0,1,0)$. Thus, the carry to the $i$-th block has to be in the form
$(1,0,0)$. Therefore, we can easily establish that the forward carry cannot
influence more than one block $(0,1,0)$ to the right.

That leaves us with proving that backward carry cannot influence too many
blocks of type B. First, we note that $Z(S_{2})$ by the property $(B)$ of the
Zeckendorf representation does not have two consecutive ones. Thus, the only
combinations available when we sum the rightmost blocks of type A (i.e. the
ones which do not have blocks of type A to the right) are:

  1. 1.

$(0,1,0)+(1,0,0)=(0,0,1)$,

  2. 2.

$(0,1,0)+(0,1,0)=(0,0,1)$ with a backward carry $1$,

  3. 3.

$(0,1,0)+(0,0,1)=(0,0,0)$ with a forward carry $1$,

  4. 4.

$(0,1,0)+(1,0,1)=(1,0,1)$ with a forward carry $1$.

The only possible backward carry happens in the second case and it is equal to
a single one on the rightmost position of the carry.

Now, observe that if the block to the left is also of type A, then a
respective block from $Z(S)$ is $(0,1,0)$ – which added to the backward carry
$(0,0,1)$ gives us forward carry to the rightmost block. And regardless of the
value of the appropriate block of $Z(S_{2})$, the total sum of the blocks and
the backward carry cannot generate any further backward carry. Finally, note
that the aforementioned forward carry resulting from backward carry appears in
the block which has to be equal to $(0,0,1)$ (as it has to be the second case
above), so it turns it into $(1,0,1)$ and it does not generate any future
carries.

Therefore, the only possible backward carry from the block of type A to the
block of type B has to be in the form $(0,0,1)$. However, this will be
combined with a block $(0,1,0)$ from $Z(S)$ – thus, the sum of the blocks from
$Z(S)$, $Z(S_{2})$ and the backward carry again cannot result in any further
backward carry.

Thus, we proved that any block of type A can affect up to one block of type B
to the left and one block of type B to the right. If there are only $2l+1$
blocks of type A, then at most $3(2l+1)$ blocks of type A and B can be
modified – and therefore at least $\frac{N}{6}-3(2l+1)$ blocks of the form
$(0,1,0)$ of $Z(S)$ remain the same even after addition of $Z(S_{2})$. This
means that $Z(S-S_{2})$ has to have at least $\frac{N}{6}-3(2L+1)$ ones –
which contradicts the assumption that $Z(S-S_{2})=Z(S_{1})$ has at most $2L+1$
ones for $L=\frac{N}{48}-1$. ∎

######  Theorem 25.

For any $N\geq 96$, any $k\in\left[0,F_{N/2-1}-\frac{N}{24}+2\right]$ and any
$l\in\left[1,\frac{N}{48}-1\right]$ there does not exist a red-blue-yellow
$(k,l)$-decomposition of $T_{N}^{F}$.

###### Proof.

A direct implication of Lemma 23 and Lemma 24 is that there does not exist a
red-blue-yellow $(k^{\prime},l)$-decomposition of $T_{N}^{F}$ such that $Y\cap
C_{1}(T^{F}_{N})=\emptyset$ for any $k^{\prime}\in[0,F_{N/2-1}]$ and
$l=\frac{N}{48}-1$.

Now, it follows from Lemma 21 that if there was a red-blue-yellow
$(k,l)$-decomposition of $T_{N}^{F}$ for $k$, then it would exist a red-blue-
yellow $(k^{\prime},l)$-decomposition of $T_{N}^{F}$ with $Y\cap
C_{1}(T^{F}_{N})=\emptyset$ and $k^{\prime}\in[0,k+2l]\subseteq[0,F_{N/2-1}]$
– thus, a contradition. ∎

Finally, we can proceed to the main theorem of this section, which shows the
existence of the trees with constant degrees such that
$BBC_{\lambda}(K_{n},T)=\max\\{n,2\lambda\\}+\Omega(\log{n})$:

######  Theorem 26.

There exists an infinite family of trees $T_{N}^{F}$ on $n=3F_{N}-2$ vertices
with $\Delta(T_{N}^{F})=3$ for $N\geq 96$ such that
$BBC_{\lambda}(K_{n},T_{N}^{F})\geq\max\\{n,2\lambda\\}+\frac{1}{48}\log_{\phi}{n}-3$
for $\lambda=\left\lfloor\frac{n}{2}\right\rfloor$.

###### Proof.

Assume that $l=\frac{N}{48}-1$. Then it always holds that
$2\lambda-n+l\leq\lambda-1$ – so in Theorem 16 we need that there cannot be
any red-blue-yellow $(k,l)$-decomposition for $k\in[0,2\lambda-n+l]$. If
$N\geq 96$, then it is easy to check that
$F_{N/2-1}-\frac{N}{24}+2>2\lambda-n+l$. Therefore, by combining Theorems 25
and 16 we get that $BBC_{\lambda}(K_{n},T_{N}^{F})>2\lambda+\frac{N}{48}-1$.
To finish the proof it is sufficient to combine this result with two simple
observations:

  * •

by assumption it holds that $2\lambda\geq\max\\{n,2\lambda\\}-1$,

  * •

by Theorem 19 it is true that
$N=\lfloor\log_{\phi}{n}\rfloor>\log_{\phi}{n}-1$.

∎

In fact, the theorem above can be proven in a more complicated, but also more
general form, i.e. that
$BBC_{\lambda}(K_{n},T_{N}^{F})>2\lambda+\frac{1}{48}\log_{\phi}{n}-2$ for all
$\lambda\in\left[\frac{n}{2}-\frac{1}{96}\log_{\phi}{n},\frac{n}{2}\right]$ –
which gives us also an additive factor over $\max\\{n,2\lambda\\}$.

##  4 Conclusion

In this paper, we presented a new bound on
$BBC_{\lambda}(K_{n},F)=\max\\{n,2\lambda\\}+\Delta^{2}(F)\lceil\log{n}\rceil$
for forests $F$ on $n$ vertices. This is the first known upper bound dependent
on the maximum degree of $F$, better than the existing ones when this
parameter is small, e.g. constant. We also showed that the same reasoning
allows us to construct a linear algorithm for finding an $\lambda$-backbone
coloring of $K_{n}$ with backbone $F$ within an additive error of
$\Delta^{2}(F)\lceil\log{n}\rceil$ from the optimum. Finally, we proved that
the bound is asymptotically tight, i.e. there exist a family of trees with
$\Delta(T)=3$ such that
$BBC_{\lambda}(K_{n},F)=\max\\{n,2\lambda\\}+\Theta(\log{n})$.

However, there remain a couple of open problems that stem from our research.
First, we can ask if the algorithm from Section 2 can be improved, i.e. does
there exist an algorithm running in polynomial time which gives us a coloring
using $BBC_{\lambda}(K_{n},F)+o(\log{n})$ colors, or even the optimal one for
certain values of $\Delta(F)$. Or maybe it is the case that finding a
$\lambda$-backbone coloring such that $BBC_{\lambda}(K_{n},F)+f(n,\Delta(F))$
for some function $f$ is $\mathcal{NP}$-hard.

Second, there arises a natural question of how to extend our result to other
classes of graphs. An obvious extension would be an analysis for a class of
split graphs, i.e. graphs that their vertices can be partitioned into a
maximum clique $C$ (of size $\omega(G)=\chi(G)$) and an independent set $I$. A
simple application of Corollary 15 gives us that

$\displaystyle BBC_{\lambda}(G,F)$
$\displaystyle\leq\lambda+BBC_{\lambda}(G[C],F[C])$
$\displaystyle\leq\lambda+\max\\{\chi(G),2\lambda\\}+\Delta^{2}(F)\lceil\log{\chi(G)}\rceil,$

as we can first solve the problem restricted to $C$, find a $\lambda$-backbone
coloring using colors from the set
$[1,\max\\{\chi(G),2\lambda\\}+\Delta^{2}(F)\lceil\log{\chi(G)}\rceil]$, and
then color all vertices in $I$ with a color
$\lambda+\max\\{\chi(G),2\lambda\\}+\Delta^{2}(F)\lceil\log{\chi(G)}\rceil$.

However, it was proved before that

######  Theorem 27 (Salman, [12]).

If $G$ is a split graph and $T$ is its spanning tree, then

$\displaystyle BBC_{\lambda}(G,T)\leq\begin{cases}1&\text{for $\chi(G)=1$,}\\\
\lambda+1&\text{for $\chi(G)=2$,}\\\ \lambda+\chi(G)&\text{for $\chi(G)\geq
3$.}\end{cases}$

This bound is tight.

Although our bound is more general, as it applies to all backbones $H$ as long
as $H[C]$ is a forest, a simple comparison of both bounds show that for trees
(and forests) our bound is worse in all cases, even for small $\lambda$ and
large $\chi(G)$. This is mainly because we assign a single color to $I$
naively instead of trying to optimize it. Still, we can pose a question: is
there a way to amend our approach to make it suitable also for split graphs
and improve the existing bound at least for some subset of graphs?

## References

  * [1] Camila Araujo, Julio Araujo, Ana Silva, and Alexandre Cezar.  Backbone coloring of graphs with galaxy backbones.  Electronic Notes in Theoretical Computer Science, 346:53–64, 2019\.
  * [2] John Adrian Bondy and Uppaluri Siva Ramachandra Murty.  Graph Theory, volume 244 of Graduate Texts in Mathematics.  Springer, 2008.
  * [3] Hajo Broersma, Fedor Fomin, Petr Golovach, and Gerhard Woeginger.  Backbone colorings for graphs: tree and path backbones.  Journal of Graph Theory, 55(2):137–152, 2007.
  * [4] Hajo Broersma, Bert Marchal, Daniel Paulusma, and A.N.M. Salman.  Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number.  Discussiones Mathematicae Graph Theory, 29(1):143–162, 2009.
  * [5] Tiziana Calamoneri.  The L(h, k)-labelling problem: an updated survey and annotated bibliography.  The Computer Journal, 54(8):1344–1371, 2011.
  * [6] Frédéric Havet, Andrew King, Mathieu Liedloff, and Ioan Todinca.  (Circular) backbone colouring: Forest backbones in planar graphs.  Discrete Applied Mathematics, 169:119–134, 2014.
  * [7] Robert Janczewski and Krzysztof Turowski.  The backbone coloring problem for bipartite backbones.  Graphs and Combinatorics, 31(5):1487–1496, 2015.
  * [8] Robert Janczewski and Krzysztof Turowski.  The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones.  Information Processing Letters, 115(2):232–236, 2015.
  * [9] Donald Knuth.  Fibonacci multiplication.  Applied Mathematics Letters, 1(1):57–60, 1988.
  * [10] Jozef Miškuf, Riste Škrekovski, and Martin Tancer.  Backbone colorings and generalized mycielski graphs.  SIAM Journal on Discrete Mathematics, 23(2):1063–1070, 2009.
  * [11] Jozef Miškuf, Riste Škrekovski, and Martin Tancer.  Backbone colorings of graphs with bounded degree.  Discrete Applied Mathematics, 158(5):534–542, 2010.
  * [12] A.N.M. Salman.  $\lambda$-backbone coloring numbers of split graphs with tree backbones.  In Proceeding of The Second IMT-GT 2006 Regional Conference on Mathematics, Statistics and Applications, pages 43–47, 2006.
  * [13] Krzysztof Turowski.  Optimal backbone coloring of split graphs with matching backbones.  Discussiones Mathematicae Graph Theory, 35(1):157–169, 2015.