On {\lambda}-backbone coloring of cliques with tree backbones in linear time

Abstract: A

l a m b d a

-backbone coloring of a graph

G

with its subgraph (also called a backbone)

H

is a function

c c o l o n V (G) i g h t a r r o w 1, d o t s, k

ensuring that

c

is a proper coloring of

G

and for each

u, v i n E (H)

it holds that

| c (u) - c (v) | g e l a m b d a

. 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

m a x n, 2 l a m b d a + D e l t a (H)^{2} l c e i l l o g n c e i l

. This result improves on the previously existing approximation algorithms as it is

(D e l t a (H)^{2} l c e i l l o g n c e i l)

-absolutely approximate, i.e. with an additive error over the optimum. We also present an infinite family of trees

T

with

D e l t a (T) = 3

for which the coloring of cliques with backbones

T

require to use at least

m a x n, 2 l a m b d a + O m e g a (l o g n)

colors for

l a m b d a

close to

f r a c n 2

.

This page was built for publication: On {\lambda}-backbone coloring of cliques with tree backbones in linear time