# Online coloring of disk graphs

Joanna Chybowska-Sokół1 Supported by the National Science Center of Poland
under Grant No. 2016/23/N/ST1/03181 Konstanty Junosza-Szaniawski1
1 Faculty of Mathematics and Information Science,
Warsaw University of Technology, Poland
email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we give a family of online algorithms for the classical
coloring problem of intersection graphs of discs with bounded diameter. Our
algorithms make use of a geometric representation of such graphs and are
inspired by an algorithm of Fiala et al., but have better competitive ratios.
The improvement comes from using two techniques of partitioning the set of
vertices before coloring them. One of which is an application of a $b$-fold
coloring of the plane. The method is more general and we show how it can be
applied to coloring other shapes on the plane as well as adjust it for online
$L(2,1)$-labeling.

keywords: disk graphs, online coloring, online $L(2,1)$-labeling, online
coloring geometric shapes

##  1 Introduction

Intersection graphs of families of geometric objects attracted much attention
of researchers both for their theoretical properties and practical
applications (c.f. McKee and McMorris [24]). For example intersection graphs
of families of discs, and in particular discs of unit diameter (called unit
disk intersection graphs), play a crucial role in modeling radio networks.
Apart from the classical coloring, other labeling schemes such as $T$-coloring
and distance-constrained labeling of such graphs are applied to frequency
assignment in radio networks [17, 28]. In this paper, we consider the
classical coloring.

We say that a graph coloring algorithm is online if the input graph is not
known a priori, but is given vertex by vertex (along with all edges adjacent
to already revealed vertices). Each vertex is colored at the moment when it is
presented and its color cannot be changed later. On the other hand, offline
coloring algorithms know the whole graph before they start assigning colors.
The online coloring can be much harder than offline coloring, even for paths.
For an offline coloring algorithm by the approximation ratio we mean the
worst-case ratio of the number of colors used by this algorithm to the
chromatic number of the graph For online algorithms, the same value is called
competitive ratio.

A unit disk intersection graph $G$ can be colored offline in polynomial time
with $3\omega(G)$ colors [27] (where $\omega(G)$ denotes the size of a maximum
clique) and online with $5\omega(G)$ colors. The last result comes from a
combination of results from [3], which states that First-Fit algorithm applied
to $K_{1,p}$-free graphs has competitive ratio at most $p-1$ with results in
[25, 27] saying that unit disc intersection graphs are $K_{1,6}$-free.

Fiala, Fishkin, and Fomin [11] presented a polynomial-time online algorithm
that finds an $L(2,1)$-labeling of an intersection graph of discs of bounded
diameter. The $L(2,1)$-labeling asks for a vertex labeling with non-negative
integers, such that adjacent vertices get labels that differ by at least two,
and vertices at distance two get different labels. The algorithm is based on a
special coloring of the plane, that resembles colorings studied by Exoo [8],
inspired by the classical Hadwiger-Nelson problem [16]. A similar idea of
reserving a set of colors for upcoming vertices can be found in the paper by
Kierstead and Trotter [22]. In [21] we described an algorithm for coloring
unit disks intersection graph. It is inspired by [11], however, we change the
algorithm in such a way that a $b$-fold coloring of the plane (see [15]) is
used instead of a classical coloring. For graphs with big $\omega$ such
approach lets us obtain the competitive ratio below $5\omega$. In this paper,
we generalize results from [21] for intersection graphs of disks with bounded
diameter. Moreover, we improve the algorithm from [21] by more uniform
distribution of vertices into layers.

Throughout the paper, we always assume that the input disk intersection graph
is given along with its geometric representation. In the paper we consider a
few algorithms for coloring $\sigma$-disk graphs (i.e. intersection graphs of
disks with a diameter within $[1,\sigma]$) and some other geometric shapes,
see Table 1. We use the divide and conquer approach. The basis of our
colorings is a coloring of the plane (except for the BranchFF algorithm, where
First-Fit is used), but we use 2 types of division of vertices of the
$\sigma$-DG. It is easiest to get a grasp on how to color disks with a
coloring of a plane by analyzing the SimpleColor algorithm. In terms of
division, algorithms BranchFF and FoldColoring show the two methods we use.
_Branching_ divides the vertices according to the size of the corresponding
disks, while _folding_ focuses on the location of their centers.

All of these algorithms can be used for online coloring of $\sigma$-disk
intersection graphs, hence we first introduce them in terms of disk colorings.
However, their application can be broader. Some can be easily adjusted for
online coloring of intersection graphs of various geometric shapes. And some
can be used for $L(2,1)$-labeling of disks or other shapes, and the only
change necessary is the coloring of the plane that we use. In the paper, we
concentrate mostly on the method itself, more than the specific parameters of
the algorithm such as competitive ratio, since they highly depend on the
input.

Again, just like for disk graphs, we assume that the geometric interpretation
of a graph is given rather than the graph itself. We also assume that some
parameters of the geometric structure are known in advance, such as the bounds
of the disk diameters. It is crucial knowledge considering our algorithms are
online and some of them are used for $L(2,1)$-labeling.

Algorithm | branching | folding | What is needed:
---|---|---|---
BranchFF[7] | Y | N | $-$
SimpleColor[11] | N | N | a solid coloring of $G_{[1,\sigma]}$
BranchColor | Y | N | a solid coloring of $G_{[1,\textbf{2}]}$
FoldColor[21] | N | Y | a $b$-fold solid coloring of $G_{[1,\sigma]}$
FoldShadeColor | N | Y | a $b$-fold solid coloring of $G_{[1,\sigma]}$, shading $\eta$
BranchFoldColor | Y | Y | a $b$-fold solid coloring of $G_{[1,\textbf{2}]}$, shading $\eta$
Table 1: A short summary of the algorithms inner methods.

##  2 Preliminaries

We start with introducing some basic definitions, notations, and preliminary
results. This section includes a method of coloring the plane, which will
later be used in our algorithms.

###  2.1 Notation

For an integer $n$, we define $[n]:=\\{1,\ldots,n\\}$. For integers $n,b$ by
$(n)_{b}$ we denote $n$ modulo $b$. By a _graph_ we mean a pair $G=(V,E)$,
where $V$ is a finite set and $E$ is a subset of the set of all 2-element
subsets of $V$. A function $c\colon V\to[k]$ is a $k$-coloring of $G=(V,E)$ if
for any $xy\in E$ holds $c(x)\neq c(y)$. By $d(u,v)$ we denote the number of
edges on the shortest $u$-$v$–path in $G$.

For a sequence of disks in the plane $(D_{i})_{i\in[n]}$ we define its
intersection graph by $G((D_{i})_{i\in[n]})=(\\{v_{i}:i\in[n]\\},E)$, where
$v_{i}$ is the center of $D_{i}$ for every $i\in[n]$ and $v_{i}v_{j}\in E$ iff
$D_{i}\cap D_{j}\neq\emptyset$. Since we have a sequence of disks rather than
a set, we disregard the fact that two disks can have the same center and
always treat vertices corresponding to different disks as separate entities.
Any graph that admits a representation by intersecting disks is called a disk
graph, or simply a DG. If the ratio between the largest and the smallest
diameters of the disks is at most $\sigma$ then we call such graph a
$\sigma$-disk graph or $\sigma$-DG, for short. We can assume that all disks in
a representation of a $\sigma$-DG are $\sigma$-disks, i.e. their diameters are
within $[1,\sigma]$. By UDG we mean the class of graphs that admit a
representation by intersecting _unit_ disks. All of our algorithms require
$\sigma$ to be known in advance. Hence we always assume to be given $\sigma$
and when we write disk graph we mean $\sigma$-DG.

For a minimization online algorithm $\mathrm{alg}$, by $\mathrm{cr(alg)}$ we
denote its _competitive ratio_ , which is the supremum of
$\frac{\mathrm{alg}(G)}{\mathrm{opt}(G)}$ over all instances $G$, where
$\mathrm{alg}(G)$ is the value of the solution given by the algorithm for
instance $G$ and $\mathrm{opt}(G)$ is the optimal solution for instance $G$.
For the classical coloring we use the fact that any coloring requires at least
$\omega(G)$ colors, where $\omega(G)$ denotes the size of the largest clique
of $G$.

###  2.2 Tilings and colorings of the plane

Our algorithms use colorings of the euclidean plane as a base for
$\sigma$-disk coloring. The coloring we use depends on the value of $\sigma$.
In this section, we present a method of finding such colorings. We start with
defining an infinite graph $G_{[1,\sigma]}$.

######  Definition 1.

By $G_{[1,\sigma]}$ we denote a graph with $\mathbb{R}^{2}$ as the vertex set
and edges between pairs of points at euclidean distance within $[1,\sigma]$.

A _coloring_ of $G_{[1,\sigma]}$ follows the regular definition of graph
coloring. For a $b$-fold colorings we include the definition with our
notation.

######  Definition 2.

A function $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ where
$\varphi_{i}:\mathbb{R}^{2}\to[k]$ for $i\in[b]$ is called a $b$-fold coloring
of $G_{[1,\sigma]}$ with color set $[k]$ if

  * •

for any point $p\in\mathbb{R}^{2}$ and $i,j\in[b]$, if $i\neq j$, then
$\varphi_{i}(p)\neq\varphi_{j}(p)$,

  * •

for any two points $p_{1},p_{2}\in\mathbb{R}^{2}$ with
$\mathop{\mathrm{dist}}(p_{1},p_{2})\in[1,\sigma]$ and $i,j\in[b]$ holds
$\varphi_{i}(p_{1})\neq\varphi_{j}(p_{2})$.

The function $\varphi_{i}$ for $i\in[b]$ is called an $i$-th layer of
$\varphi$.

Notice that a coloring of $G_{[1,\sigma]}$ is a 1-fold coloring of
$G_{[1,\sigma]}$.

Coloring and $b$-fold colorings of $G_{[1,\sigma]}$ have been a subject of
various papers ([8],[16],[9],[15], [29]). The case of $\sigma=1$ is the most
studied, as the problem of coloring $G_{[1,1}$ is known as Hadwiger-Nelson
problem. For many years the best bounds on $\chi(G_{[1,1})$ were 4 and 7,
which are quite easy to obtain. A breakthrough came in 2018, when Aubrey de
Grey [6] proved, that $\chi(G_{[1,1})\geq 5$. Right after that, a paper by
Exoo and Ismailescu [10] claimed the same result (the proofs were not the
same). Since then there was a spike of interest in various colorings of the
plane. The size of a minimal subgraph of $G_{[1,1}$ with chromatic number
equal 5 became one of the subjects of study as well [19].

In our case, we only consider colorings based on specific tilings of the plane
(i.e. we partition the plane into congruent shapes called tiles). To emphasize
this we will call such colorings _solid_. The assumption of our plane coloring
being solid will be clearly stated in our theorems.

In general, a coloring $\varphi$ of $G_{[1,\sigma]}$ is called solid if there
exists a tiling such that each tile is monochromatic (so the diameter of a
tile cannot exceed 1) and tiles in the same color are at distance greater than
$\sigma$. A $b$-fold coloring $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ of
the plane is called solid if for all $i\in[b]$ the coloring $\varphi_{i}$ is
solid and tiles in the same color (possibly from different tilings) are at
distance greater than $\sigma$. An example of a solid 1-fold 7-coloring of the
plane (by John Isbell [29]) is presented in Figure 1(c).

Now we introduce our method of building solid $b$-fold colorings of the plane.
Note that it is possible to construct other solid colorings that could be used
for our algorithms, but finding them is not the main problem of the paper.

We define an $h^{2}$-fold coloring of the plane based on hexagonal tilings,
for any positive integer $h$. For $h=1$ it is a coloring of the plane as
presented in [5] and we follow the notation from both [5] and [21]. From this
point onward we will assume $h$ to be a fixed positive integer and often omit
it in further notation.

Let us start with defining the tiling. Let $H_{0,0}$ be a hexagon with two
vertical sides, center in $(0,0)$, diameter equal one, and part of the
boundary removed as in Figure 1(a). Note that the width of $H_{0,0}$ equals
$\frac{\sqrt{3}}{2}$. Then let $s_{1}=[\frac{\sqrt{3}}{2},0]$, and
$s_{2}=[\frac{\sqrt{3}}{4},-\frac{3}{4}]$. For $i,j\in\mathbb{Z}$ let
$H_{i,j}$ be a _tile_ created by shifting $H_{0,0}$ by a vector
$i\cdot\frac{s_{1}}{h}+j\cdot\frac{s_{2}}{h}$, namely
$H_{i,j}:=\\{(x,y)+i\cdot\frac{s_{1}}{h}+j\cdot\frac{s_{2}}{h}\in\mathbb{R}^{2}:\
(x,y)\in H_{0,0}\\}$. Notice that if $h=1$ then
$\\{H_{i,j}:i,j\in\mathbb{Z}\\}$ forms a partition of the plane, which we call
a hexagonal tiling. More generally for any $m\in[h^{2}]$ the set
$L_{m}=\\{H_{i,j}:1+(i)_{h}+h(j)_{h}=m\\}$ forms a tiling (see Figure 1(b)),
we call it the _$m$ -th layer_.

(a) A tile $H_{i,j}$.

(b) Hexagonal tiling - the 1${}^{\text{st}}$ layer.

(c) 7-coloring of the plane

Figure 1: [21] Hexagonal tiling.

All points in a single tile will share a color. Now for a triple of non-
negative integers $(h^{2},p,q)$ we define a coloring such that for any
$(i,j)\in\mathbb{Z}^{2}$ hexagons $H_{i,j},H_{i+p,j+q},H_{i+p+q,j-p}$ have the
same color. Notice that the centers of such three hexagons form an equilateral
triangle (see the three hexagons on the right side of Figure 2). By reapplying
this rule of a single colored triangles we obtain that sets of the form
$\\{H_{i+k\cdot p+l\cdot(p+q),j+k\cdot q-l\cdot p}:\ k,l\in\mathbb{Z}\\}$ are
monochromatic. When maximal monochromatic sets are of this form we call such
coloring a $(h^{2},p,q)$-coloring.

######  Lemma 3.

A $(h^{2},p,q)$-coloring uses $p^{2}+pq+q^{2}$ colors.

###### Proof.

Let us denote greatest common divisor of $p$ and $q$ as $d$ and let
$p^{\prime}=p/d$, $q^{\prime}=q/d$.

We call the set of $H_{i,j}$, $i\in\mathbb{Z}$, the $j$-th row of tiles. Let
us call the color of $H_{0,0}$ blue and $\mathcal{T}=\\{H_{k\cdot
p+l\cdot(p+q),k\cdot q-l\cdot p}:\ k,l\in\mathbb{Z}\\}$ denote the set of all
blue hexagons. To give some insight of where $\mathcal{T}$ comes from let $v$
denote a vector from $(0,0)$ to the center of $H_{p,q}$
($v=p\cdot\frac{s_{1}}{h}+q\cdot\frac{s_{2}}{h}$) and $\overline{v}$ be a
vector obtained from $v$ via rotating it by $\frac{\pi}{3}$
($\overline{v}=p\cdot\frac{s_{1}-s_{2}}{h}+q\cdot\frac{s_{1}}{h}=(p+q)\cdot\frac{s_{1}}{h}-p\cdot\frac{s_{2}}{h}$)
- see Figure 2. Then $\mathcal{T}$ is a set of all tiles created by shifting
$H_{0,0}$ by $kv+l\overline{v}$, for $k,l\in\mathbb{Z}$.

Figure 2: A single color in a $(1,2,1)$-coloring. The angle between $v$ and
$\overline{v}$ does not depend on the values of $h,p,q$.

First let us notice that, by the definition of $\mathcal{T}$, blue appears in
rows numbered by $k\cdot q-l\cdot p=(kq^{\prime}-lp^{\prime})\cdot d$, for any
$k,l\in\mathbb{Z}$. Since $p^{\prime}$ and $q^{\prime}$ are coprime,
$\\{kq^{\prime}-lp^{\prime}:\ k,l\in\mathbb{Z}\\}=\mathbb{Z}$. Then blue
appears in a row iff its number is divisible by $d$.

Note that, since we used the same pattern (only shifted) for every color, we
have the same number of colors in every row. Hence the total number of colors
equals the number of colors used in a single row multiplied by $d$.

To find the number of colors used in a row, it is enough to know how often
does a single color reappear in it (see example in Figure 1(c) in one row
every 7${}^{\text{th}}$ hexagon is blue and we use 7 colors in each row).

Let $m$ be the smallest positive number such that $H_{m,0}$ is colored blue.
Since $H_{m,0}\in\mathcal{T}$, then there exist integers $k,l$ such that:

$\displaystyle k\cdot p+l\cdot(p+q)=m,$ (1) $\displaystyle k\cdot q-l\cdot
p=0.$ (2)

From (2) we derive $kq^{\prime}=lp^{\prime}$. Since $p^{\prime},\ q^{\prime}$
are coprime, then $k$ is divisible by $p^{\prime}$ and $l$ by $q^{\prime}$.
Moreover $p^{\prime},\ q^{\prime}$ are both non-negative, hence either $k$ and
$l$ are both non-positive or they are both non-negative. Without loss of
generality we assume the latter. Hence
$m=d\cdot(kp^{\prime}+lq^{\prime}+lp^{\prime})$ is minimal when $k=p^{\prime}$
and $l=q^{\prime}$. So the numbers of colors in a row equals
$m=d(p^{\prime}p^{\prime}+q^{\prime}q^{\prime}+p^{\prime}q^{\prime})$, and
from our previous remarks we conclude that the total number of colors equals
$d^{2}(p^{\prime}p^{\prime}+q^{\prime}q^{\prime}+p^{\prime}q^{\prime})=p^{2}+q^{2}+pq$.
∎

In case $q=0$ we can easily express the number of colors we use in terms of
$\sigma$, which was done in [15] (see Figure 3). It is enough to take
$p=\lceil(\frac{2\sigma}{\sqrt{3}}+1)\cdot h\rceil$, as then the distance
between centers of $H_{0,0}$ and $H_{p,0}$ equals
$|p\cdot\frac{s1}{h}|=\lceil(\frac{2\sigma}{\sqrt{3}}+1)h\rceil\cdot\frac{\sqrt{3}}{2h}\geq\sigma+\frac{\sqrt{3}}{2}$.
Since these tiles are in the same row, then the distance between them is in
fact the distance between their vertical sides and equals the distance between
the centers minus $\frac{\sqrt{3}}{2}$.

######  Proposition 4 ([15]).

For $h\in\mathbb{N_{+}}$ there exists a solid $h^{2}$-fold coloring $\varphi$
of $G_{[1,\sigma]}$ with $\left\lceil(\frac{2\sigma}{\sqrt{3}}+1)\cdot
h\right\rceil^{2}$ colors.

Figure 3: [21] $h^{2}$-fold coloring of the plane by Grytczuk, Junosza-
Szaniawski, Sokół, Węsek

In more general case it is a bit hard to find the maximal $\sigma$ such that
the $(h^{2},p,q)$-coloring is a coloring of $G_{[1,\sigma]}$. $\sigma$ for
$(h^{2},p,q)$-coloring. For some values of $(h^{2},p,q)$ such $\sigma$ might
not exist at all, since the distance between two tiles of the same color could
be smaller than 1. It is enough to consider the distance between $H_{0,0}$ and
$H_{p,q}$, but this value depends on which points in these two tiles minimize
the distance. When computing the maximal sigma we consider the distances
between any two points on the boundaries of $H_{0,0}$ and $H_{p,q}$. The
minimal distance we find is the maximal value of However we can easily find
some values of $\sigma$ for which the $(h^{2},p,q)$-coloring works.

######  Proposition 5.

For any fixed values of $h,p,q$, let
$\sigma=\frac{\sqrt{3}}{2h}\sqrt{p^{2}+pq+q^{2}}-1$. If $\sigma\geq 1$, then
the $(h^{2},p,q)$-coloring is a coloring of $G_{[1,\sigma]}$.

###### Proof.

Let as consider the minimal distance between two points $P_{1}\in H_{0,0}$ and
$P_{2}\in H_{p,q}$. Let us denote the centers of these tiles as $C_{1}$ and
$C_{2}$. By the definition of $H_{i,j}$, the distance between $C_{1}$ and
$C_{2}$ equals
$|p\cdot\frac{s_{1}}{h}+q\cdot\frac{s_{2}}{h}|=|\frac{1}{h}[p\frac{\sqrt{3}}{2}+q\frac{\sqrt{3}}{4},-q\frac{3}{4}]|=\frac{1}{h}\sqrt{((2p+q)\frac{\sqrt{3}}{4})^{2}+(-q\frac{3}{4})^{2}}=\frac{\sqrt{3}}{2h}\sqrt{p^{2}+pq+q^{2}}$.
The distance between $P_{1}$ and $C_{1}$ is at most $\frac{1}{2}$, and the
same is true for $P_{2}$ and $C_{2}$. Hence the distance between any $P_{1}\in
H_{0,0}$ and $P_{2}\in H_{p,q}$ is at most
$\frac{\sqrt{3}}{2h}\sqrt{p^{2}+pq+q^{2}}-1=\sigma\geq 1$.

Any two points of the same color are either both in one tile - then their
distance is smaller than $1$, or in two tiles of the same color. The distance
between any two tiles of the same color is at least as big as the distance
between $H_{0,0}$ and $H_{p,q}$ (by the construction of
$(h^{2},p,q)$-coloring). Hence in the latter case the distance between such
points is at least $\frac{\sqrt{3}}{2h}\sqrt{p^{2}+pq+q^{2}}-1$, which
concludes the proof. ∎

In most cases it is possible to use $(h^{2},p,q)$ colorings for $\sigma$
larger than stated above, but the Proposition shows the approximate value. Now
by Lemma 3 and Proposition 5 we obtain the following.

######  Corollary 6.

For any fixed values of $h,p,q$, let $k=p^{2}+pq+q^{2}$ and
$\sigma=\frac{\sqrt{3}}{2h}\sqrt{k}-1$. If $\sigma\geq 1$, then the
$(h^{2},p,q)$-coloring is an $h^{2}$-fold $k$-coloring of $G_{[1,\sigma]}$.

By this corollary we get that $k\approx\frac{4h^{2}}{3}(\sigma+1)^{2}$. This
is a worse result then the one from Proposition 4. However if we consider the
maximal values of $\sigma$ for some cases $(h^{2},p,q)$-colorings we get
better results. In particular one of the best $h^{2}$-fold colorings of
$G_{[1,2]}$ and ’small’ values of $h$ is the $(8^{2},1,26)$-coloring, which
uses 703 colors. More examples of precise values of $\sigma$ are presented in
Table 2. It contains only the best $(h^{2},p,q)$-colorings for
$h\in\\{1,2,3\\}$ and $\sigma$ up to 3.

$\sigma$ | $\frac{k}{h^{2}}$ | $h^{2}$ | $k$ | $p$ | $q$
---|---|---|---|---|---
1.01036 | 4.77778 | 9 | 43 | 1 | 6
1.08253 | 5.25 | 4 | 21 | 1 | 4
1.1547 | 5.44444 | 9 | 49 | 0 | 7
1.29904 | 6.33333 | 9 | 57 | 1 | 7
1.32288 | 7. | 9 | 63 | 3 | 6
1.44338 | 7.11111 | 9 | 64 | 0 | 8
1.51554 | 7.75 | 4 | 31 | 1 | 5
1.58771 | 8.11111 | 9 | 73 | 1 | 8
1.60728 | 8.77778 | 9 | 79 | 3 | 7
1.63936 | 9.25 | 4 | 37 | 3 | 4
1.73205 | 9.33333 | 9 | 84 | 2 | 8
1.75 | 9.75 | 4 | 39 | 2 | 5
1.87639 | 10.1111 | 9 | 91 | 1 | 9
1.94856 | 10.75 | 4 | 43 | 1 | 6
2.02073 | 11.1111 | 9 | 100 | 0 | 10
2.02073 | 12.1111 | 9 | 109 | 5 | 7

$\sigma$ | $\frac{k}{h^{2}}$ | $h^{2}$ | $k$ | $p$ | $q$
---|---|---|---|---|---
2.04634 | 12.25 | 4 | 49 | 3 | 5
2.16506 | 12.3333 | 9 | 111 | 1 | 10
2.17945 | 13. | 9 | 117 | 3 | 9
2.3094 | 13.4444 | 9 | 121 | 0 | 11
2.38157 | 14.25 | 4 | 57 | 1 | 7
2.45374 | 14.7778 | 9 | 133 | 1 | 11
2.46644 | 15.4444 | 9 | 139 | 3 | 10
2.59808 | 16.3333 | 9 | 147 | 2 | 11
2.61008 | 16.75 | 4 | 67 | 2 | 7
2.64575 | 17.3333 | 9 | 156 | 4 | 10
2.74241 | 17.4444 | 9 | 157 | 1 | 12
2.75379 | 18.1111 | 9 | 163 | 3 | 11
2.81458 | 18.25 | 4 | 73 | 1 | 8
2.88675 | 18.7778 | 9 | 169 | 0 | 13
2.92973 | 20.1111 | 9 | 181 | 4 | 11
3.03109 | 20.3333 | 9 | 183 | 1 | 13

Table 2: A few records of $(h^{2},p,q)$-coloring. $k$ denotes the number of
colors and is equal $p^{2}+pq+q^{2}$.

The last thing we should know about our colorings is the number of subtiles in
a tile. Having $b$ tilings (in our case $b=h^{2}$), by a subtile we mean a
non-empty intersection of $b$ tiles, one from each layer. By
$\gamma=\gamma(\varphi)$ we denote the maximum number of subtiles in a single
tile in a solid $b$-fold coloring of the plane $\varphi$.

######  Lemma 7 ([21]).

The number of subtiles in any tile in the set $\\{H_{i,j}:i,j\in\mathbb{Z}\\}$
is equal to: $\gamma=1$ for $h=1$, $\gamma=12$ for $h=2$, $\gamma=6h^{2}$ for
$h>2$.

Notice that for any $h$, the number above is no larger than $6h^{2}$. In the
next chapters, we will usually write about $b$-fold colorings, rather than
$h^{2}$-fold colorings, since one could apply different colorings, then
mentioned in this section. However, when the bound on the number of colors is
given, substituting $\gamma$ for $6b$ might give a bit of extra insight.

###  2.3 $L^{*}(2,1)$-labeling of the plane

######  Definition 8.

A solid $b$-fold $k$-coloring $\varphi$ of $G_{[1,\sigma]}$ is called a solid
$b$-fold $L^{*}(2,1)$-labeling of $G_{[1,\sigma]}$ with $k$ labels, if

  1. 1.

all labels (colors) are in $\\{1,2,\ldots,k\\}$, or all are in $\\{0,1,\ldots
k-1\\}$,

  2. 2.

for any two tiles $T_{1},T_{2}$ with the same color, $T_{1}$ and $T_{2}$ are
at point-to-point distance greater than $2\sigma$.

  3. 3.

for any two tiles $T_{1},T_{2}$ with consecutive colors, $T_{1}$ and $T_{2}$
are at point-to-point distance greater than $\sigma$

  4. 4.

for a tile $T_{1}$ with the smallest color and a tile $T_{2}$ with the largest
color, $T_{1}$ and $T_{2}$ are at point-to-point distance greater than
$\sigma$.

Note that by this definition any two points of the same tile must still be
lower than $1$.

Such labeling were briefly considered in [11] (called ’circular labeling’) and
more thoroughly in case of $\sigma=1$ in [21]. Fiala, Fishkin, and Fomin state
in [11] that $L^{*}(2,1)$-labelings can always be found, give the estimated
time of searching, and give an example of such coloring for
$\sigma=\frac{\sqrt{7}}{2}$. Grytczuk, Junosza-Szaniawski, Sokół, and Węsek in
[21] concentrate on finding such $b$-fold labelings for $\sigma=1$, and in
particular, give a method of constructing them in case $b=h^{2}$.

######  Theorem 9 ([21]).

For all $h\in\mathbb{N}$, there exists a solid $h^{2}$-fold
$L^{*}(2,1)$-labeling of $G_{[1,1]}$ with $k=3\lceil
h(\frac{2}{\sqrt{3}}+1)+1\rceil^{2}+1$ labels.

Figure 4: [21] A solid $h^{2}$-fold $L^{*}(2,1)$-labeling of $G_{[1,1]}$

The construction is quite similar to the one from Proposition 4. The key idea
is to substitute a single color of $(h^{2},p,0)$-coloring, where $p=\lceil
h(\frac{2}{\sqrt{3}}+1)+1\rceil$, with 3 consecutive labels (see Figure 4).
Tiles of such triplets of labels are monochromatic in $(h^{2},p,0)$-coloring,
hence their distances are bigger than 1. The tiles with the same label are at
distance larger than 2. The fact that $p$ is larger than $\lceil
h(\frac{2}{\sqrt{3}}+1)\rceil$ by 1 is enough to make sure that tiles with
consecutive labels from different triplets are at distance greater than 1 (see
labels $3\varrho-1$ and $3\varrho$ in Fig. 4). Naturally, in such
construction, we use labels from 1 to $p^{2}$, but the declared number of
labels is $p^{2}$+1, hence there is no conflict between the smallest and
largest labels.

We can do the same for $\sigma\in[1,\frac{1}{4-2\sqrt{3}}]$ as well. The upper
bound on $\sigma$ here comes from the restriction on tiles with the same label
(by the second condition of the definition, their distance must be greater
than $2\sigma$). The centers of such tiles are at distance
$|p\cdot\frac{s_{1}}{h}+p\cdot\frac{s_{2}}{h}|=\frac{p}{h}|s_{1}+s_{2}|=\frac{3p}{2h}$
and we need this value to be greater than $2\sigma+1$.

######  Proposition 10.

If $1\leq\sigma\leq\frac{1}{4-2\sqrt{3}}\approx 1.86603$, then for all
$h\in\mathbb{N}$, there exists a solid $h^{2}$-fold $L^{*}(2,1)$-labeling of
$G_{[1,\sigma]}$ with $k=3\lceil h(\frac{2\sigma}{\sqrt{3}}+1)+1\rceil^{2}+1$
labels.

Figure 5: A solid $h^{2}$-fold $L^{*}(2,1)$-labeling of $G_{[1,\sigma]}$

The issue of the distance between two tiles of the same label could be fixed
in two ways. The first one is to choose a larger $p$. The other is to simply
label monochromatic sets with 6 consecutive labels as in Figure 5. It is easy
to notice that in this case, the distances between tiles of the same label are
at least $2\sigma+\frac{\sqrt{3}}{2}>2\sigma$.

######  Corollary 11.

For all $h\in\mathbb{N}$, there exists a solid $h^{2}$-fold
$L^{*}(2,1)$-labeling of $G_{[1,\sigma]}$ with $k=6\lceil
h(\frac{2\sigma}{\sqrt{3}}+1)+1\rceil^{2}+1$ colors.

Increasing $p$ and labeling monochromatic sets with 3 labels should give a
smaller number of labels $k$, but the full analysis of correctness is quite
tedious. For now, we are content with Corollary 11, since our main aim is to
show that some of our online coloring algorithms can be used for
$L(2,1)$-labeling disk graphs. The important fact to note is that a $b$-fold
$L^{*}(2,1)$-labelings of $G_{[1,\sigma]}$ with $k$ labels, can have smaller
ratio $k/b$ then the number of labels in $1$-fold $L^{*}(2,1)$-labeling.

It is also worth considering whether there is a more general method of
constructing solid $b$-fold $L^{*}(2,1)$-labelings of $G_{[1,\sigma]}$, much
like $(h^{2},p,q)$-colorings. While it is possible to find a method that is
more general than what we have shown, it should still have some rigid details.
One way to do that is to keep labeling monochromatic sets of
$(h^{2},p,q)$-colorings with multiple labels, but without setting $q=0$.

##  3 Basic coloring algorithms

The algorithms are online so they color the vertex $v_{i}$ corresponding to
the disk $D_{i}$ knowing only disks $D_{1},\ldots,D_{i}$. Once the vertex
$v_{i}$ is colored it cannot be recolored.

First let us introduce the algorithm by Erlebach and Fiala [7] (with a slight
change in assignment of $j$, which will be described below), which divides the
set of vertices of a disk graph according to the diameters of the
corresponding disks.

1 foreach  _$i\in[n]$_ do

2 Read $D_{i}$, let $v_{i}$ be the center of $D_{i}$

3 if  _$\sigma_{i}=\sigma=2^{t},\ t\in\mathbb{Z}_{+}$_ then

4 $j\leftarrow\lfloor\log_{2}\sigma_{i}\rfloor-1$

5 else

6 $j\leftarrow\lfloor\log_{2}\sigma_{i}\rfloor$

7 $B_{j}:=B_{j}\cup\\{v_{i}\\}$

8 $F:=\\{c(v_{k}):1\leq k<i,v_{k}\in B_{j},D_{k}\cap
D_{i}\neq\emptyset\\}\cup\ \\{c(v_{k}):1\leq k<i,v_{k}\notin L_{j}\\}$ (the
set of forbidden colors)

9 $c(v_{i}):=min(N\setminus F)$

return _$c$_

Algorithm 1 $BranchFF((D_{i})_{i\in[n]}$)

Notice that the algorithm uses a separate set of colors for each set $B_{j}$.
Since for any $j$ the set $B_{j}$ consists of disks with diameters within
$[2^{j},2^{j+1}]$, so the ratio of the largest and the smallest diameters is
at most 2. This holds in particular in the case of $\sigma=2^{t},\
t\in\mathbb{Z}_{+}$, when the maximal $j$ equals $t-1$ and $B_{t-1}$ consists
of disks of diameter $[2^{t-1},2^{t}]$. The unusual assignment of $j$ in such
cases lets us avoid creating a separate set $B_{t}$ consisting solely of disks
with a diameter equal $sigma$. Now we can apply the following.

######  Lemma 12 ([7]).

The FirstFit coloring algorithm is 28-competitive on disks of diameter ratio
bounded by two.

Since $j$ takes values from $0$ to $\lfloor\log_{2}\sigma\rfloor$ (or
$\lfloor\log_{2}\sigma\rfloor-1$ for $\sigma=2^{t}$), there are at most
$\lceil\log_{2}\sigma\rceil$ sets $B_{j}$ with distinct sets of colors. Each
of $B_{j}$ is colored with no more than $28\chi_{j}\leq 28\chi(G)$, where
$\chi_{j}$ stands for the minimal number of colors required to color a graph
induced by $B_{j}$. Hence the following stands.

######  Lemma 13.

$BranchFF$ is $28\lceil\log_{2}\sigma\rceil$-competitive for $\sigma$-disk
graphs.

Now we present another way of dividing vertices of a disk graph by Fiala,
Fishkin, and Fomin [11]. The input of the algorithm is a solid coloring
$\varphi$ of $G_{[1,\sigma]}$ and a sequence of the disks of diameters within
$[1,\sigma]$. The idea of the algorithm is the following: find the tile of
$\varphi$ containing the center of $D_{i}$. The color of a vertex
corresponding to $D_{i}$ is the smallest available color equal modulo $k$ to
the color of the tile containing the center of $D_{i}$.

1 foreach  _$i\in[n]$_ do

2 Read $D_{i}$, let $v_{i}$ be the center of $D_{i}$

3 let $T(v_{i})$ be the tile containing $v_{i}$

4 $t(v_{i})\leftarrow|\\{v_{1},\ldots v_{i-1}\\}\cap T(v_{i})|$

5 $c(v_{i})\leftarrow\varphi(v_{i})+k\cdot t(v_{i})$

return _$c$_

Algorithm 2 $SimpleColor_{\varphi}$($(D_{i})_{i\in[n]}$)

The following theorem is a special case of a result from [11]. It is also a
special case of Theorem 20 of this paper. The number of colors follows from
the fact that all vertices from a single tile create a clique, hence
$t(v_{i})\leq\omega(G)-1$, for any $i\in[n]$.

######  Theorem 14 (Fiala, Fishkin, Fomin [11]).

Let $\varphi$ be a solid $k$-coloring of $G_{[1,\sigma]}$ and
$(D_{i})_{i\in[n]}$ sequence of $\sigma$-disks. Algorithm
$SimpleColor_{\varphi}((D_{i})_{i\in[n]})$ returns coloring of
$G=G((D_{i})_{i\in[n]})$ with at most $k\cdot\omega(G)$ colors.

######  Corollary 15.

For a unit disk graph $G=G((D_{i})_{i\in[n]})$ and a 7-coloring of the plane
$\varphi$ from the picture 1(c) the coefficient ratio of the algorithm
$SimpleColor_{\varphi}((D_{i})_{i\in[n]})$ is 7.

###### Proof.

$\mathrm{cr}(SimpleColor_{\varphi}((D_{i})_{i\in[n]})\leq\frac{7\omega(G)}{\omega(G)}=7$.
∎

######  Corollary 16.

For a $\sigma$-disk graph $G=G((D_{i})_{i\in[n]})$ and a coloring of
$G_{[1,\sigma]}$ from Proposition 4 the coefficient ratio of the algorithm
$SimpleColor_{\varphi}((D_{i})_{i\in[n]})$ is
$\lceil\frac{2\sigma}{\sqrt{3}}+1\rceil^{2}$.

In the case of UDGs, the competitive ratio of $SimpleColoring$ is worse than
that of FirstFit algorithm. In the next part of the paper, we consider more
complex algorithms with a better ratio that are based on the same principles
as $BranchFF$ and $SimpleColor$.

The next algorithm is a combination of the two above. Just like the $BranchFF$
it divides vertices according to the diameters but instead of coloring every
$B_{j}$ with the smallest safe color, much like the FirstFit algorithm, we
color them according to $SimpleColor$ algorithm. First we need a solid
$12$-coloring $\varphi$ of $G_{[1,2]}$. Then for any
$j\in[0,log_{2}(\sigma)]\cap\mathbb{N}$ we define $\varphi_{j}$ to be a
coloring of $G_{[2^{j},2^{j+1}]}$ that is scaled copy of $\varphi$. The color
of a vertex is a pair $(j,c)$ where $j$ is the number assigned by branching
and $c$ is the color based on $\varphi_{j}$. It could easily be changed so
that the color is a number, but in the case of graph coloring we only consider
how many colors are used and we believe leaving the color as a pair makes the
method more clear.

1 foreach  _$i\in[n]$_ do

2 Read $D_{i}$, let $v_{i}$ be the center of $D_{i}$

3 if  _$\sigma_{i}=\sigma=2^{t},\ t\in\mathbb{Z}_{+}$_ then

4 $j(v_{i})\leftarrow\lfloor\log_{2}\sigma_{i}\rfloor-1$

5 else

6 $j(v_{i})\leftarrow\lfloor\log_{2}\sigma_{i}\rfloor$

7 $B_{j}:=B_{j}\cup\\{v_{i}\\}$

8 let $T(v_{i})$ be the tile of $\varphi_{j}$ containing $v_{i}$

9 $t(v_{i})\leftarrow|\\{v_{1},\ldots v_{i-1}\\}\cap T(v_{i})|$

10 $c(v_{i})\leftarrow(j,\varphi_{j}(v_{i})+12\cdot t(v_{i}))$

return _$c$_

Algorithm 3 $BranchColor_{(\varphi_{j})}((D_{i})_{i\in[n]}$)

######  Theorem 17.

Let $(\varphi_{j})$ be a sequence of solid $12$-colorings of
$G_{[2^{j},2^{j+1}]}$ for $j\in[0,log_{2}(\sigma)]\cap\mathbb{N}$, and
$(D_{i})_{i\in[n]}$ sequence of $\sigma$-disks. Algorithm
$BranchColor_{(\varphi_{j})}((D_{i})_{i\in[n]})$ returns a coloring of
$G=G((D_{i})_{i\in[n]})$ with at most
$12\lceil\log_{2}(\sigma)\rceil\cdot\omega(G)$ colors.

###### Proof.

First let us prove that $c$ is indeed a coloring of $G$. Consider any two
centers of disks $v_{i1}$ and $v_{i2}$ at euclidean distance at most $\sigma$.
If $j(v_{i1})\neq j(v_{i2})$ then the first terms of $c(v_{i1})$ and
$c(v_{i2})$ differ. Otherwise $j(v_{i1})=j(v_{i2})=:j$ and the distance
between $v_{i1}$ and $v_{i2}$ is at most $2^{j+1}$. If
$T_{j}(v_{i1})=T_{j}(v_{i2})$ then $\varphi_{j}(v_{i1})=\varphi_{j}(v_{i2})$
but $t(v_{i})\neq t(v_{j})$, and by formula in line 3 we get
$c(v_{i})\neq(c_{j})$. If $T_{j}(v_{i1})\neq T_{j}(v_{i2})$ then the distance
between $v_{i1}$ and $v_{i2}$ belongs to $[2^{j},2^{j+1}]$, hence
$\varphi_{j}(v_{i1})\neq\varphi_{j}(v_{i2})$ and $c(v_{i1})\neq c(v_{i2})$.
Now let us consider the number of colors. For a fixed $j$, all the vertices
from $B_{j}$ has the same first term. Let us consider $v_{i}$ with the highest
second term. Since $\varphi_{j}$ is a 12-coloring then
$\varphi_{j}(v_{i})+12\cdot t(v_{i})\leq 12\cdot(t(v_{i})+1)$. Since all
vertices from $T(v_{i})$ create a clique, and there are already $t(v_{i})+1$
of them when $v_{i}$ is being colored, we obtain $t(v_{i})+1\leq\omega(G)$.
Hence the second term of $c(v_{i})$ is less or equal to $12\omega(G)$. Since
there are at most $\lceil\log_{2}(\sigma)\rceil$ values of $j$ (see
explanation above lemma 13) and for each $j$ we have at most $12\omega(G)$
second terms of $c$, we use no more than $\lceil\log_{2}(\sigma)\rceil\cdot
12\omega(G)$. ∎

######  Corollary 18.

For any sequence of $\sigma$-disks $(D_{i})_{i\in[n]}$ and $(\varphi_{i})$ as
on Theorem 17, we have $cr(BranchColor_{(\varphi_{j})}((D_{i})_{i\in[n]}))\leq
12\lceil\log_{2}(\sigma)\rceil$.

For the three algorithms we presented so far, clearly the $BranchColor$ has
the best competitive ratio for ’large’ $\sigma$. Since the competitive ratio
of $SimpleColor$ depends on the choice of coloring of the plane, which in turn
depends on $\sigma$, it is a bit hard to pinpoint the exact value of $\sigma$
where $BranchColor$ becomes better than $SimpleColor$. However
$cr(SimpleColor)$ is quadratic in terms of $\sigma$, no matter the choice of
coloring of $G_{[1,\sigma]}$. Figure 6 shows the competitive ratios of the
algorithms, where we take coloring of $G_{[1,\sigma]}$ from Proposition 4 for
$SimpleColor$.

Figure 6: A comparison of competitive ratios of algorithms $BranchFF$,
$SimpleColor$ (with colorings of the plane from Proposition 4), $BranchColor$.

##  4 Algorithms with _folding_

The next algorithm $FoldColor$ follows the same idea as $SimpleColor$, with a
difference that it uses $b$-fold coloring instead of the classical coloring of
the plane. It was introduced by Junosza-Szaniawski, Sokół, Rzążewski, and
Węsek [21] as a coloring algorithm for unit disk graphs, however, it can also
be applied for the more general case of $\sigma$-disk graphs, with different
colorings of the plane. The algorithm goes as follows. We start with some
fixed solid $b$-fold coloring $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ of
$G_{[1,\sigma]}$ with colors $[k$]. When a disk $D_{i}$ is read, it is
assigned to a single tile from the coloring in two steps. First, we find all
tiles that contain the center $v_{i}$ of $D_{i}$. Then we choose one of the
$b$ layers of $\varphi$ for $D_{i}$ and call it $\ell(v_{i})$ (we try to
distribute disks to layers as uniformly as possible). By doing so we choose a
single tile $T$ from that layer containing $v_{i}$. We count the number of
previous vertices assigned to this tile - $t(v_{i})$. Then $v_{i}$ is colored
with the color of this tile plus $k$ times the number of previous vertices of
$T$.

Notice that for $b=1$ the algorithm $Color_{\varphi}$ is the same as
$SimpleColor_{\varphi}$.

1 foreach  _$i\in[n]$_ do

2 Read $D_{i}$, let $v_{i}$ be the center of $D_{i}$

3 foreach  _$r\in[b]$_ do

4 let $T_{r}(v_{i})$ be the tile from the layer $r$ containing $v_{i}$

5 $\ell(v_{i})\leftarrow 1+(|\\{v_{1},\ldots
v_{i-1}\\}\cap\bigcap_{r\in[b]}T_{r}(v_{i})|)_{b}$

6 $t(v_{i})\leftarrow|\\{u\in\\{v_{1},\ldots v_{i-1}\\}\cap
T_{\ell(v_{i})}(v_{i}):\ell(u)=\ell(v_{i})\\}|$

7 $c(v_{i})\leftarrow\varphi_{\ell(v_{i})}(v_{i})+k\cdot t(v_{i})$

return _$c$_

Algorithm 4 $FoldColor_{\varphi}((D_{i})_{i\in[n]}$)

The following Theorem can be found in the paper by Junosza-Szaniawski et al.
[21], where only colorings of Unit Disk Graphs are considered. Hence we adjust
the proof for our case of $\sigma$-DGs. The bound on the number of colors
remains unchanged, as it relies directly on $k$ rather than on $\sigma$ (but
naturally $k$ grows along with $\sigma$).

######  Theorem 19.

Let $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ be a solid $b$-fold
$k$-coloring of $G_{[1,\sigma]}$, and $(D_{i})_{i\in[n]}$ sequence of
$\sigma$-disks. Algorithm $FoldColor_{\varphi}((D_{i})_{i\in[n]}$) returns
coloring of $G=G((D_{i})_{i\in[n]})$.

###### Proof.

Consider any two centers of disks $v_{i}$ and $v_{j}$ at euclidean distance at
most $\sigma$. If $T_{\ell(v_{i})}(v_{i})=T_{\ell(v_{j})}(v_{j})$ then
$\varphi_{\ell(v_{i})}(v_{i})=\varphi_{\ell(v_{j})}(v_{j})$ but $t(v_{i})\neq
t(v_{j})$ and by formula in line 4 we get $c(v_{i})\neq(c_{j})$. If
$T_{\ell(v_{i})}(v_{i})\neq T_{\ell(v_{j})}(v_{j})$ then either
$\ell(v_{i})\neq\ell(v_{j})$ or the distance between $v_{i}$ and $v_{j}$ is
within $[1,\sigma]$. Hence
$\varphi_{\ell(v_{i})}(v_{i})\neq\varphi_{\ell(v_{j})}(v_{j})$ and
$c(v_{i})\neq c(v_{j})$. ∎

######  Theorem 20 (Junosza-Szaniawski et al. [21]).

Let $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ be a solid $b$-fold
$k$-coloring of $G_{[1,\sigma]}$, and $(D_{i})_{i\in[n]}$ sequence of
$\sigma$-disks. Algorithm $FoldColor_{\varphi}((D_{i})_{i\in[n]})$ returns
coloring of $G=G((D_{i})_{i\in[n]})$ with the largest color at most
$k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma}{b}\right\rfloor$, where
$\gamma$ is the maximum number of subtiles in one tile of $\varphi$.

Proof of a slightly improved result will be included below, hence we omit this
one.

Notice that, by Lemma 7,
$k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma}{b}\right\rfloor\leq
k\cdot\left\lfloor\frac{\omega(G)}{b}+6(b-1)\right\rfloor\leq\frac{k}{b}\cdot\omega(G)+6k(b-1)$.
It shows that the algorithms competitive ratio is close to $\frac{k}{b}$ for
graphs with large $\omega(G)$. But we are at a disadvantage if the graph has a
small clique size, especially when $\sigma$ is big, as $\frac{k}{b}$ is
quadratic in terms of $\sigma$. In the case of UDGs with relatively large
clique size ($\omega(G)\geq 108901$ for a $25$-fold coloring from [21]) the
algorithm, $FoldColor$ has a competitive ratio lower than $5$, which was the
previous best, obtained by $FirstFit$. The fact that $FirstFit$ can be beaten
by $FoldColor$ is especially interesting for us since later in this paper we
replace the $FirstFit$ part of $BranchFF$ with $FoldColor$.

Now we will slightly improve the $FoldColor$ algorithm by better distributing
the vertices among layers. This change will be carried on to the next
algorithm as well. Notice that in line 4 of the algorithm
$FoldColor_{\varphi}((D_{i})_{i\in[n]})$ the first vertex in each subtile is
assigned to the first layer. Hence in each tile the numbers of vertices from
the first and last layers can differ by $\gamma$. To lessen this difference we
can distribute vertices among layers in a way closer to uniform. To do so we
need the following definition.

######  Definition 21.

Let $\varphi$ be a solid coloring of $G_{[1,\sigma]}$ with $\gamma$ subtiles
in each tile. A function $\eta$ assigning a number from $[b]$ to each subtile
is called _shading_ of $\varphi$ if in every tile the numbers of subtiles with
the same value of $\eta$ are the same.

Figure 7: Example of a shading for tiling with $h=3$

Notice that the shading does not depend on the coloring $\varphi$ but rather
on the tiling that it is based on. For the hexagonal tilings defined in
section 2.2, such shading exists (see an example on Figure 7). The
construction for $h\geq 3$ is based on a fact that the vertical borders of the
hexagons create line of the form $x=s\cdot\frac{\sqrt{3}}{4h}$, where
$s\in\mathbb{Z}$ (it follows from the proof of Lemma 7 presented in [21]). It
gives a partition of the plane into vertical stripes - each of these is
assigned $h$ shades in a cyclic manner: choose any stripe to be the _first_
one - it receives shades $\\{1,2,...,h\\}$, the one next to it receives shades
$\\{h+1,...,2h\\}$ and so on. Each stripe is divided into diamonds (again by
the borders of the hexagons), consisting of two subtiles. We assign shades to
the diamonds in a cyclic manner. It is easy to align the stripes in such a way
that every hexagon has exactly 6 triangular subtiles of each shade.

For given solid coloring $\varphi$ of $G_{[1,\sigma]}$ and its shading $\eta$
we can define an improved algorithm
$FoldShadeColor_{\varphi,\eta}((D_{i})_{i\in[n]})$. It is an algorithm
obtained from $FoldColor_{\varphi}((D_{i})_{i\in[n]})$ by replacing line 4
with
$\ell(v_{i})\leftarrow\eta(\bigcap_{r\in[b]}T_{r}(v_{i}))+(|\\{v_{1},\ldots
v_{i-1}\\}\cap\bigcap_{r\in[b]}T_{r}(v_{i})|)_{b}$ (so the very first vertex
from a subtile with shade equal $t$ is assigned to the $t$-th layer).

######  Theorem 22.

Let $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ be a solid $b$-fold
$k$-coloring of $G_{[1,\sigma]}$, $\eta$-shading, and $(D_{i})_{i\in[n]}$
sequence of disks. Algorithm
$FoldShadeColor_{\varphi,\eta}((D_{i})_{i\in[n]}$) returns coloring of
$G=G((D_{i})_{i\in[n]})$ with the largest color at most
$k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma/2}{b}\right\rfloor$, where
$\gamma$ is the maximum number of subtiles in one tile of $\varphi$.

###### Proof.

The proof is analogous to the proof of Theorem 20[21] with a difference in the
estimation of $\omega(G)$.

Let $v_{i}$ be a vertex that got the biggest color. Consider the moment of the
course of the algorithm when vertex $v_{i}$ was colored. Let
$\ell_{i}=\ell(v_{i}),$ and $t(v_{i}),c(v_{i})$ be defined as in the
algorithm. Let $T=T_{\ell_{i}}$ be the tile from the $\ell_{i}$-th layer
containing $v_{i}$. Let $S_{1},\ldots S_{\gamma}$ be subtiles of $T$. Let
$s_{q}=|\\{u\in\\{v_{1},\ldots v_{i}\\}:u\in S_{q}\\}|$ and
$s_{q}(\ell_{i})=|\\{u\in\\{v_{1},\ldots v_{i}\\}:u\in
S_{q},\ell(u)=\ell_{i}\\}|$ for $q\in[\gamma]$. So the number of all vertices
assigned to layer $\ell_{i}$ and tile $T$ before $v_{i}$ equals
$t(v_{i})=\sum_{q=1}^{\gamma}s_{q}(\ell_{i})-1$.

Now let us look closely at the values of $s_{q}$ in terms of
$s_{q}(\ell_{i})$. We denote $(x)_{b}:=x\mod b$. Vertices in $S_{q}$ are
assigned to layers in a cyclic manner starting from $\eta(S_{q})$ and there
are $(\ell_{i}-\eta(S_{q}))_{b}$ of them before the first one is assigned to
layer $\ell_{i}$ (if such vertex exists). Then we know that there are
$s_{q}(\ell_{i})$ vertices in $S_{q}$ assigned to $\ell_{i}$, so there are at
least $b(s_{q}(\ell_{i})-1)+1$ vertices across all layers. Hence $s_{q}\geq
b(s_{q}(\ell_{i})-1)+(\ell_{i}-\eta(S_{q}))_{b}+1$ (if $s_{q}(\ell_{i})=0$ the
right side of the inequality is negative while the left side is non-negative,
so it holds).

Now we are ready to estimate the number of all vertices from
$\\{v_{1},\ldots,v_{i}\\}$ contained in $T$ (but not necesarily assigned to
the layer $\ell_{i}$). Notice that these vertices are pairwise at distance
less than one and hence they form a clique. After summing both sides of the
last inequality over $q$ from 1 to $\gamma$ we obtain

$\omega(G)\geq\sum_{q=1}^{\gamma}s_{q}\geq\sum_{q=1}^{\gamma}[b(s_{q}(\ell_{i})-1)+(\ell_{i}-\eta(S_{q}))_{b}+1]=$

$b\sum_{q=1}^{\gamma}s_{q}(\ell_{i})-b\gamma+\sum_{q=1}^{\gamma}(\ell_{i}-\eta(S_{q}))_{b}+\gamma\overset{(*)}{=}$

$\overset{(*)}{=}b(t(v_{i})+1)-(b-1)\gamma+\frac{\gamma}{b}\sum_{j=0}^{b-1}j=$

$=b(t(v_{i})+1)-(b-1)\gamma+\frac{\gamma}{b}\frac{b(b-1)}{2}=b(t(v_{i})+1)-(b-1)\gamma/2$

Notice that since $\eta$ is a shading of $\varphi$ the number of subtiles in
the tile $T$ with each shade from 1 to $b$ is the same. Thus
$(\ell_{i}-\eta(S_{q}))_{b}$ admits each of the values from 0 to $b-1$ for the
same number of subtiles, namely $\gamma/b$. This explains equality $(*)$.

From the estimation above we obtain that $t(v_{i})+1$ is at most
$\left\lfloor\frac{\omega(G)+(b-1)\gamma/2}{b}\right\rfloor$. Since we chose
$v_{i}$ to have the biggest color and the total number of colors equals at
most $c(v_{i})=k(t(v_{i})+1)$. ∎

In our algorithms it is crucial to construct good $b$-fold colorings of
$G_{[1,\sigma]}$. We already showed a method for constructing such colorings.
However the best possible $(h^{2},p,q)$-coloring depends highly on the value
of $\sigma$. Thus it is hard to give best attainable bounds on the competitive
ratio without specifying $\sigma$. Hence we use Corollary 4 to give some
proper bounds on the competitive ratio of our algorithms, although for most
values of $\sigma$ it is possible to lower them by adjusting the coloring of
$(G_{[1,\sigma]})$.

######  Corollary 23.

For the $h^{2}$-fold $\varphi$ coloring of the plane from Theorem 4 and any
sequence of $\sigma$-disks $(D_{i})_{i\in[n]}$ let
$\omega=\omega(G((D_{i})_{i\in[n]}))$. Then

$\mathrm{cr}(FoldColor_{\varphi}((D_{i})_{i\in[n]}))\leq\frac{\left\lceil(\frac{2\sigma}{\sqrt{3}}+1)\cdot
h\right\rceil^{2}}{\omega}\cdot\left\lfloor\frac{\omega+(h^{2}-1)6h^{2}}{h^{2}}\right\rfloor$

and

$\mathrm{cr}(FoldShadeColor_{\varphi,\eta}((D_{i})_{i\in[n]}))\leq\frac{\left\lceil(\frac{2\sigma}{\sqrt{3}}+1)\cdot
h\right\rceil^{2}}{\omega}\cdot\left\lfloor\frac{\omega+(h^{2}-1)3h^{2}}{h^{2}}\right\rfloor,$

Hence the ratios are of order
$\left(\frac{2\sigma}{\sqrt{3}}+1\right)^{2}+O\left(\frac{1}{h}\right)+O\left(\frac{h^{4}}{\omega}\right).$

Figure 8: Competitive ratio of $FoldShadeColor$ for $\sigma$-DG, $\sigma=1$ or
$\sigma=2$, depending on $\omega$, with $\varphi$ as $h^{2}$-fold colorings
where $h=1,2$ or $3$. Figure 9: Competitive ratio of $FoldShadeColor$ for
$\sigma$-DG with $\omega=10^{9}$ depending on $\sigma$, with $\varphi$ as
$h^{2}$-fold colorings where $h=10$.

So the algorithm $FoldShadeColor$ has a better competitive ratio than
$FoldColor$, however competitive ratios of both algorithms are equal
asymptotically. Notice that for $h=5$ and unit disk graphs $G$ with
$\omega(G)\geq 108901$, the competitive ratio of the algorithm $FoldColor$ is
less than $5$, hence lower than the ratio of the FirstFit. For the algorithm
$FoldShadeColor$ with $h=5$ the ratio is below 5 for UDG with $\omega\geq
54450$ (and occasionally for smaller $\omega$, because of the floor function
in our bound). See Figures 8, 9 to study the changes in ratio depending on
$\omega$, $\sigma$ and $h$.

The last algorithm $BranchFoldColor_{\varphi,\eta}$ joins all the techniques
from the previous ones. The vertices are dived in two steps as in
$BranchColor$ but rather than coloring of $B_{j}$ by using a regular coloring
of the plane we use a $b$-fold coloring of $G_{[1,2]}$ and a shading $\eta$
much like in the $FoldShadeColor{\varphi,\eta}$ algorithm.

1 foreach  _$i\in[n]$_ do

2 Read $D_{i}$, let $v_{i}$ be the center of $D_{i}$

3 if  _$\sigma_{i}=\sigma=2^{t},\ t\in\mathbb{Z}_{+}$_ then

4 $j(v_{i})\leftarrow\lfloor\log_{2}\sigma_{i}\rfloor-1$

5 else

6 $j(v_{i})\leftarrow\lfloor\log_{2}\sigma_{i}\rfloor$

7 $B_{j}:=B_{j}\cup\\{v_{i}\\}$

8 foreach  _$r\in[b]$_ do

9 let $T_{r}(v_{i})$ be the tile from the layer $r$ containing $v_{i}$

10 $\ell(v_{i})\leftarrow\eta(\bigcap_{r\in[b]}T_{r}(v_{i}))+(|\\{v_{1},\ldots
v_{i-1}\\}\cap\bigcap_{r\in[b]}T_{r}(v_{i})|)_{b}$

11 $t(v_{i})\leftarrow|\\{u\in\\{v_{1},\ldots v_{i-1}\\}\cap
T_{\ell(v_{i})}(v_{i}):\ell(u)=\ell(v_{i})\\}|$

12 $c(v_{i})\leftarrow(j,\varphi_{\ell(v_{i})}(v_{i})+k\cdot t(v_{i}))$

return _$c$_

Algorithm 5 $BranchFoldColor_{\varphi,\eta}((D_{i})_{i\in[n]}$)

######  Theorem 24.

Let $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ be a solid $b$-fold
$k$-coloring of $G_{[1,2]}$, $\eta$-shading, and $(D_{i})_{i\in[n]}$ sequence
of disks. Algorithm $BranchFoldColor_{\varphi,\eta}((D_{i})_{i\in[n]}$)
returns coloring of $G=G((D_{i})_{i\in[n]})$ with the largest color at most
$\lceil\log_{2}(\sigma)\rceil\cdot
k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma/2}{b}\right\rfloor$, where
$\gamma$ is the maximum number of subtiles in one tile of $\varphi$.

###### Proof.

As in previous algorithms the branching partitions vertices into sets $B_{j}$
and colors each of these sets separately. The first element of the color of a
vertex is the index of its set, hence there cannot be a conflict of colors
between vertices from different branching sets. The second part of the color
of a vertex comes from the same procedure as in algorithm $FoldShadeColor$,
hence it gives a proper coloring of a graph induced by $B_{j}$ and the maximal
value it takes is at most
$k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma/2}{b}\right\rfloor$. Since
there are at most $\lceil\log_{2}(\sigma)\rceil$ sets $B_{j}$, we obtain the
stated bound. ∎

The number of colors in this algorithm looks very similar to the one for
$FoldShadeColor$, except for multiplying by $\lceil\log_{2}(\sigma)\rceil$.
But it can be significantly smaller, since the values of $k$ and $b$
correspond to the coloring of $G_{[1,2]}$ instead of $G_{[1,\sigma]}$ (and
with the same $b$ the value of $k$ is quadratic in terms of $\sigma$).

By using the fact that $\gamma\leq 6b$ we obtain the following simplified
bound.

######  Corollary 25.

The competitive ratio of $BranchFoldColor$ is at most:

$\frac{\lceil\log_{2}(\sigma)\rceil\cdot
k\lfloor\frac{\omega(G)}{b}+3(b-1)\rfloor}{\omega(G)}=O(\log_{2}(\sigma)\cdot\frac{k}{b})$

.

Lets consider a function $f(b)$ that gives the the best possible value of
$k/b^{\prime}$ for all $b^{\prime}$-fold $k$-colorings of $G_{[1,2]}$ with
$b^{\prime}\leq b$. Not only is it non-increasing, but also the value
decreases from time to time. However, if we want a small competitive ratio of
the algorithm, then clearly $\omega(G)$ should be large compared to $b$. For
that reason, we should only consider small values of $b$. In the table below,
we have chosen three _good_ $b$-fold colorings of $G_{[1,2]}$. The last column
shows the minimal value of $\omega(G)$ where the upper bound on the number of
colors is smaller than for the coloring from the previous row. Of course, the
algorithm still works for smaller values of $\omega$ than the ones given
below, but it is simply not the best option in such cases.

Table 3: The first 3 columns correspond to the parameters of chosen colorings of $G_{[1,2]}$ (the best we get for $b=h^{2}\leq 100$). The last column shows the minimal values of $\omega(G)$, where the competitive ratio of $BranchFoldColor_{\varphi,\eta}$ is smaller then for the previous row. $b$ | $k$ | $\frac{k}{b}$ | $\omega$
---|---|---|---
1 | 12 | 12 |
9 | 100 | 11.11 | 2700
64 | 703 | 10.98 | $1.02944\cdot 10^{6}$

##  5 Coloring various shapes

Many classes of intersection graphs of geometric shapes are considered in
research papers. In particular, there is plenty of information available in
the case of intersection graphs of axis-parallel rectangles. However, in this
paper, we concentrate on the scaling aspect of shapes. In this section, we
consider the online coloring of any convex shape. In fact, the methods we
present could be applied to some non-convex shapes as well, but in general, it
might not bring the best number of colors.

Let us first consider an intersection graph $G$ of similar copies of a convex
shape $S$ \- scaling by the factor less or equal $\sigma$, translation,
rotation, and reflection are allowed. We assume that $S$ is the smallest of
all similar copies. One natural method of online coloring such graphs would be
to first find circumscribed circles for all shapes in $G$. Then we "fill them
in" - substitute shapes with disks that contain them, and color a resulting
supergraph $H$ of $G$, which is a disk graph. All these operations can be done
in an online setting. Unfortunately, the offline parameters of the supergraph
$H$ may vary from those of the original graph $G$. In particular, the clique
number may increase significantly. Hence if we were to calculate the ratio of
diameters of $H$ and use one of our algorithms the number of colors will be
expressed using $\omega(H)$, rather than $\omega(G)$, and we cannot tell what
the competitive ratio of said algorithm would be. Fortunately, we can avoid
such problems if every shape is replaced by a pair of disks.

To adapt our method for each shape $S$ we consider two disks with common
center: $ID(S)$ \- inner disk and $OD(S)$ \- outer disk (described below, see
Figure 10). To be more precise we start with the given shape $S$ and choose a
_center of $S$_ to be an interior point $P$. It is best if the choice of $P$
minimizes the ratio between the diameters of the outer and inner disks with
centers in $P$. Just as we did with disks we will associate the centers of
shapes with their corresponding vertices. The _outer disk_ is the smallest
disk with the center in $P$ that contains shape $S$. The _inner disk_ is the
largest disk with the center in $P$ contained in shape $S$. Let us call the
diameters of $OD(S)$ and $ID(S)$ as outer and inner diameters, respectively,
and denote their ratio as $\rho$. Without loss of generality, we can assume
that the inner diameter of $S$ equals one and the outer $\rho$. Taking a
similar copy of $S$ the translation, rotation and reflection do not effect the
diameters. Since we allow scaling by a maximal factor of $\sigma$ and $S$ is
the smallest of all copies, then all inner diameters are in $[1,\sigma]$ and
all outer ones in $[\rho,\rho\cdot\sigma]$.

Figure 10: Inner and outer disks of $S$. A rotated copy of $S$ has the same
disks.

Notice that if two shapes intersect so do their outer disks. On the other
hand, if two inner disks intersect so do their original shapes. Using these
two simple facts we can find a coloring of the plane that can be used as a
basis for an online coloring algorithm. If each tile of our coloring has
diameter 1, as the inner diameter of $S$, then all shapes with centers in a
single tile form a clique. Moreover, if tiles of the same color are at
distance greater than $\rho\cdot\sigma$, then two shapes with centers in two
same-colored tiles cannot intersect. Hence we are interested in $b$-fold
coloring of $G_{[1,\rho\cdot\sigma]}$. With such coloring, we can use the
$FoldShadeColor$ algorithm.

######  Corollary 26.

Let $(S_{i})_{i\in[n]}$ sequence of shapes similar to $S$ with the ratio of
outer and inner equal $\rho$. Let $\varphi=(\varphi_{1},\ldots,\varphi_{b})$
be a solid $b$-fold $k$-coloring of $G_{[1,\rho\cdot\sigma]}$. Algorithm
$FoldShadeColor_{\varphi}((S_{i})_{i\in[n]})$ returns coloring of
$G=G((S_{i})_{i\in[n]})$ with the largest color at most
$k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma/2}{b}\right\rfloor$, where
$\gamma$ is the number of subtiles in one tile of $\varphi$.

###### Proof.

The proof of such coloring being proper is the same as in Theorem 19 (just
change the wold disk to shape and $\sigma$ to $\rho\cdot\sigma$).

The number of colors is copied from Theorem 22. It follows from the estimation
on $\omega(G)$, which is a result of the fact that all vertices from a single
tile form a clique. It is still true for shapes, hence the value remains. ∎

Notice that if we take $\sigma=1$, there is no scaling involved, hence there
is no way of branching. Yet we still need a $b$-fold coloring of
$G_{[1,\rho]}$. That is the reason why we include a general method of finding
such colorings of the plane instead of considering only colorings of
$G_{[1,2]}$. It also shows that the number of colors in our online coloring of
$G$ depends highly on the value of $\rho$, which is why we try to minimize it
with the choice of the center of $S$. For larger values of $\sigma$ however,
the branching method is possible. Consider $\sigma_{i}$ to be the inner
diameter of shape $S_{i}$, and use a $b$-fold coloring of $G_{[1,2\rho]}$.
Then with branching on $\sigma_{i}$ we obtain the following.

######  Corollary 27.

Let $(S_{i})_{i\in[n]}$ sequence of shapes similar to $S$ with the ratio of
outer and inner equal $\rho$. Let $\varphi=(\varphi_{1},\ldots,\varphi_{b})$
be a solid $b$-fold $k$-coloring of $G_{[1,2\rho]}$. Algorithm
$BranchFoldColor_{\varphi}((S_{i})_{i\in[n]})$ returns coloring of
$G=G((S_{i})_{i\in[n]})$ with the largest color at most $\lceil
log(\sigma)\rceil
k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma/2}{b}\right\rfloor$, where
$\gamma$ is the number of subtiles in one tile of $\varphi$.

The last thing to point out is that our approach of online coloring similar
shapes does not require shapes to be similar at all! In fact it is enough that
all shapes from our sequence $(S_{i})_{i\in[n]}$ have centers and disks
$ID(S_{i})$ and $OD(S_{i})$ with diameters in $[1,\sigma]$ (or in any interval
$[m,M]$ with $m,M\in\mathbb{R}_{+}$, $m<M$, since we can scale them all).
Hence branching and coloring based on the coloring of a plane is a very
general method.

##  6 $L(2,1)$-labeling of disks

In this section, we consider online $L(2,1)$-labeling of $\sigma$-disk graphs,
which is a special case of coloring with integer values. Let us first recall
the definition (quite often the labeling is defined starting with the value of
0, but it is more convenient for us to use positive integers only instead).

######  Definition 28.

Formally, an $L(2,1)$-labeling of a graph $G$ is any function
$c:V\to\\{1,\ldots,k\\}$ such that

  1. 1.

$|c(v)-c(w)|\geq 1$ for all $v,w\in V(G)$ such that $d(u,w)=2$ (we call such
pairs _second neighbors_),

  2. 2.

$|c(v)-c(w)|\geq 2$ for all $v,w\in V(G)$ such that $vw\in E(G)$.

The value $k-1$ is called a _span_ of the labeling.

The $L(2,1)$-span of a graph $G$, denoted by $\lambda(G)$, is the minimum span
of an $L(2,1)$-labeling of $G$. The number of available labels is
$\lambda(G)+1$, but some may be not used.

$L(2,1)$-labeling was introduced by Griggs and Yeh [14] who proved that
$\lambda(G)\leq\Delta^{2}+2\Delta$ and conjectured $\lambda(G)\leq\Delta^{2}$,
which became known as the $\Delta^{2}$-conjecture. $L(2,1)$-labeling was
consider for various classes of graphs [1, 2, 12, 20].

Not all graphs can be effectively $L(2,1)$-labeled _online_ , since once you
have two vertices of the same color, the next vertex could be the neighbor of
them both, and thus the labeling would be faulty. However, having a geometric
representation of a graph with some conditions can exclude those situations
from happening. In those cases, we consider the competitive ratio as the ratio
of the highest labels of online and offline labelings. Hence our maximal label
is compared with $\lambda(G)+1$, and since $\lambda(G)+1\geq 2\omega(G)+1$,
bounding the maximal label by a function of $\omega(G)$ is very convenient.
Fiala, Fishkin and Fomin [11] studied $L(2,1)$-labelings of disk graphs. One
of their results states the following.

######  Lemma 29.

[11] There is no constant competitive online $L(2,1)$-labeling algorithm for
the class of $\sigma$-disk graphs unless there is an upper bound on $\sigma$
and any $\sigma$-disk graph occurs as a sequence of disks in the online input.

This result follows from the fact that in online $L(2,1)$-labeling once we
color vertex $v$ with $c(v)$, the color $c(v)$ is not available for any
current or future second neighbors. For that reason, we need to know whether a
pair of vertices might become second neighbors in the future, and this is
where the location of disks and the bounds on their diameters plays a role. If
the centers of two disks are $C_{1},C_{2}$ and the diameters $d_{1}$ and
$d_{2}$, they can become second neighbors iff
$\mathop{\mathrm{dist}}(C_{1},C_{2})\leq\frac{d_{1}+d_{2}}{2}+\sigma$.

Now we will consider which of the presented online coloring algorithms may be
adjusted for $L(2,1)$-labelings. Firstly, we know that $SimpleColor$ can be
used for online $L(2,1)$-labeling as it was presented in [11]. The algorithm
itself remains unchanged, but we need to use a special coloring of the plane,
which we call solid $L(2,1)$-coloring of the plane.

In case of unit disks it was proven in [21] that $FoldColor_{\varphi}$ gives
proper $L(2,1)$-labeling as long as $\varphi$ is a solid $b$-fold
$L^{*}(2,1)$-labeling of $G_{[1,1]}$ with $k$ labels.

There is no reason for the algorithm to stop working properly for larger
$\sigma$. Shading also does not spoil the labeling. Hence we get that
$FoldShadeColor_{\varphi,\eta}$ ’works’ for $L(2,1)$-labeling $\sigma$-disk
graphs.

######  Theorem 30.

Let $\varphi=(\varphi_{1},\ldots,\varphi_{b})$ be a solid $b$-fold
$L^{*}(2,1)$-labeling of $G_{[1,\sigma]}$ with $k$ labels, $\eta$-shading, and
$(D_{i})_{i\in[n]}$ sequence of $\sigma$-disks. The algorithm
$FoldShadeColor_{\varphi}((D_{i})_{i\in[n]})$ returns an $L(2,1)$-coloring of
$G=G((D_{i})_{i\in[n]})$ with the largest label not exceeding
$k\cdot\left\lfloor\frac{\omega(G)+(b-1)\gamma/2}{b}\right\rfloor$.

###### Proof.

First, we prove the correctness of the algorithm. Consider any two centers of
disks $v_{i}$ and $v_{j}$ with the same label. Notice that
$T_{\ell(v_{i})}(v_{i})\neq T_{\ell(v_{j})}(v_{j})$, because otherwise
$t(v_{i})\neq t(v_{j})$ and thus $c(v_{i})\neq c(v_{j})$. Since
$\varphi_{\ell(v_{i})}(v_{i})=\varphi_{\ell(v_{j})}(v_{j})$ and $\varphi$ is
an $L^{*}(2,1)$-labeling of $G_{[1,\sigma]}$, $T_{\ell(v_{i})}(v_{i})$ and
$T_{\ell(v_{j})}(v_{j})$ are at point-to-point distance greater than
$2\sigma$. Hence $v_{i}$ and $v_{j}$ are at Euclidean distance greater than
$2\sigma$ and thus are neither neighbors nor have a neighbor in common.

Now consider two centers of disks $v_{i}$ and $v_{j}$ labeled with consecutive
numbers. Without loss of generality assume that $c(v_{i})+1=c(v_{j})$. Then
$\varphi_{\ell(v_{i})}(v_{i})+1=\varphi_{\ell(v_{j})}(v_{j})$ or
$\varphi_{\ell(v_{i})}(v_{i})=k$ and $\varphi_{\ell(v_{j})}(v_{j})=1$. Since
$\varphi$ is an $L^{*}(2,1)$-labeling of the plane, $T_{\ell(v_{i})}(v_{i})$
and $T_{\ell(v_{j})}(v_{j})$ are at point-to-point distance greater than
$\sigma$. Hence $v_{i}$ and $v_{j}$ are at Euclidean distance greater than
$\sigma$ and are not adjacent. The bound on the largest color follows directly
from Theorem 22. ∎

The use of $b$-fold labelings of $G_{[1,\sigma]}$ instead limiting ourselves
to $1$-fold labelings might give significant improvement of the number of
labels in labeling of $G=G((D_{i})_{i\in[n]})$, just as it did in case of
colorings. We have shown in section 2.3 that the required solid labelings of
$G_{[1,\sigma]}$ exist for any $\sigma$.

Now let us consider the branching technique. While branching vertices we
partition them according to their diameters into sets $B_{j}$ and color each
set separately. This approach will not work with $L(2,1)$-labeling, since we
cannot easily reserve a set of labels for each $B_{j}$ in advance. Since the
labels of adjacent vertices must differ by at least 2, and vertices from sets
$B_{i},\ B_{j}$, $i\neq j$, can be neighbors, we would need to make sure that
there is no pair of consecutive labels between $B_{i}$ and $B_{j}$. Adding to
that, second neighbors must have different labels, and their common neighbor
might be in a different set $B_{j}$ than either of them. Hence to the best of
our knowledge, the $FoldShadeColor$ algorithm might be the best one for online
$L(2,1)$-labeling $\sigma$-disk graphs.

Moreover, $FoldShadeColor$ can also be applied for online $L(2,1)$-labeling
shapes with bounded inner and outer diameters. It is necessary to choose the
appropriate coloring of the plane, as we did in the case of the online
coloring of shapes, namely a solid $L^{*}(2,1)$-labeling of
$G_{[1,\rho\cdot\sigma]}$.

##  7 Concluding remarks

We have considered a few algorithms which use some sort of coloring of the
plane as a basis for online coloring geometric intersection graphs. As we have
shown they can be applied not only for disk coloring but also the online
coloring of series of shapes. Since there are many ways of modifying the
coloring of the plane, there are many online coloring problems that could be
approached with our methods. $L(2,1)$-labeling of $\sigma$-disks and shapes is
just one of them.

Moreover, the same methods could be applied in other dimensions. One may
consider a solid $b$-fold colorings of a line as a basis for online coloring,
as in [4]. The same could be done in higher dimensions, where for instance a
solid coloring of $\mathbb{R}^{3}$ could serve for coloring intersection
graphs of 3-dimensional balls and other three-dimensional solid objects. We
must however always have bounds on the size of considered objects.

## References

  * [1] H. L. Bodlaender, T. Kloks, R. B. Tan, J. van Leeuwen, Approximations for lambda-Colorings of Graphs, Comput. J. 47(2) pp. 193–204, 2004.
  * [2] T. Calamoneri, The $L(h,k)$-Labelling Problem: An Updated Survey and Annotated Bibliography, Comput. J., 54: 1344–1371, 2011.
  * [3] A. Capponi, C. Pilloto, On-line coloring and on-line partitioning of graphs. Manuscript 2003.
  * [4] J. Chybowska-Sokół, G. Gutowski, K. Junosza-Szaniawski, P. Mikos, A. Polak, Online Coloring of Short Intervals, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), Leibniz International Proceedings in Informatics (LIPIcs),52:1–52:18, 2020.
  * [5] J. Chybowska-Sokół, K. Junosza-Szaniawski, K. Węsek, Coloring distance graphs on the plane, in review.
  * [6] A.D.N.J. de Grey, The chromatic number of the plane is at least 5, 2018. arXiv:1804.02385
  * [7] T. Erlebach, J. Fiala, On-line coloring of geometric intersection graphs, Computational Geometry, 23: 243–255, 2002.
  * [8] G. Exoo, $\varepsilon$-Unit Distance Graphs, Discrete Comput. Geom., 33: 117–123, 2005.
  * [9] K.J. Falconer: The realization of distances in measurable subsets covering Rn. J. Comb. Theory, Ser. A 31, 187–189, 1981.
  * [10] G. Exoo, D. Ismailescu, The chromatic number of the plane is at least 5 - a new proof, 2018. arXiv:1805.00157
  * [11] J. Fiala, A. Fishkin, F. Fomin, On distance constrained labeling of disk graphs, Theoretical Computer Science 326: 261–292, 2004.
  * [12] J.P. Georges, D.W. Mauro, On the size of graphs labeled with a condition at distance two, J. Graph Theory 22, pp. 47-–57, 1996.
  * [13] D. Gonçalves, On the $L(p,1)$-labelling of graphs. Discrete Mathematics 308: 1405–1414, 2008.
  * [14] J.R. Griggs, R.K. Yeh, Labeling graphs with a condition at distance two, SIAM J. Discrete Math., 5: 586–595, 1992.
  * [15] J. Grytczuk, K. Junosza-Szaniawski, J. Sokół, K. Węsek, Fractional and $j$-fold coloring of the plane, Disc. & Comp. Geom. , Volume 55, Issue 3, 594–-609 (2016).
  * [16] H. Hadwiger, Ungeloste Probleme, Elemente der Mathematik, 16: 103–104, 1961.
  * [17] W.K. Hale, Frequency assignment: Theory and applications, Proc. IEEE, 68: 1497–1514, 1980.
  * [18] R. Hochberg, P. O’Donnell, A large independent set in the unit distance graph.Geombinatorics 3(4), 83-–84, 1993.
  * [19] M. J. H. Heule, Computing Small Unit-Distance Graphs with Chromatic Number 5, 2018. arXiv:805.12181
  * [20] J. van den Heuvel, R.A. Leese, M.A. Shepherd, Graph labeling and radio channel assignment, J. Graph Theory 29, pp. 263-–283, 1998.
  * [21] K. Junosza-Szaniawski, J. Sokół, P. Rzążewski, Online coloring and $L(2,1)$-labeling of unit disk intersection graphs to appear.
  * [22] H.A. Kierstead, W.T. Trotter, An extremal problem in recursive combinatorics. Congr. Numerantium 33: 143–153, 1981.
  * [23] H.A. Kierstead, D.A. Smith, W.T. Trotter, First-Fit coloring on interval graphs has performance ratio at least 5, European Journal of Combinatorics 51: 236–254, 2016.
  * [24] T.A. McKee, F.R. McMorris, Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications, vol. 2, SIAM, Philadelphia, 1999.
  * [25] E. Malesińska, Graph theoretical models for frequency assignment problems, Ph.D. Thesis, Technical University of Berlin, Germany, 1997.
  * [26] J. Parts, The chromatic number of the plane is at least 5 – a human-verifiable proof, 2020. arXiv:2010.12661
  * [27] R. Peeters, On coloring $j$-unit sphere graphs, Technical Report, Department of Economics, Tilburg University, 1991.
  * [28] F.S. Roberts, $T$-colorings of graphs: Recent results and open problems, Disc. Math., 93: 229–245, 1991.
  * [29] A. Soifer, The Mathematical Coloring Book. Springer, New York, 2008.
  * [30] Z. Shao, R. Yeh, K.K. Poon, W.C. Shiu, The $L(2,1)$-labeling of $K_{1,n}$-free graphs and its applications. Applied Math. Letters, 21: 1188–1193, 2008.