A tight analysis of Kierstead-Trotter algorithm
for online unit interval coloring
Tetsuya Araki, Koji M. Kobayashi

arXiv:1609.09031v1 [] 28 Sep 2016

Abstract
Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an
optimal online algorithm for the online interval coloring problem. In this paper, for online unit
interval coloring, we show that the number of colors used by the Kierstead-Trotter algorithm is
at most 3ω(G) − 3, where ω(G) is the size of the maximum clique in a given graph G, and it is
the best possible.

1

Introduction

The online interval coloring problem has been extensively studied for many years. Research on this
problem is motivated by applications such as resource allocation in communication networks.
Online interval coloring is defined as follows: given any interval graph G = (V, E), an online
algorithm does not have any information on G at first. Intervals of G are revealed to the online
algorithm one by one over time (the length of an interval is one for the unit interval coloring, which
we study in this paper). The algorithm must assign a color to a revealed interval before the next
one is revealed such that any two intersecting intervals are not colored by the same color. The
cost of an algorithm is the number of colors used to color intervals of G and the objective of this
problem is to minimize the number of used colors. Note that the number of colors used by an
optimal offline algorithm is the size of the maximum clique in G, which is denoted as ω(G).
Previous Results and Our Results. For any interval graph G, Kierstead and Trotter [9]
designed an online algorithm and proved the number of colors used by the algorithm is at most
3ω(G) − 2. Moreover, they showed an instance such that the number of colors by any online
algorithm is at least 3ω(G) − 2. Thus, their online algorithm is optimal for online interval coloring.
There are various lengths of intervals in this instance, which means that it cannot be applied to
the case in which the lengths are restricted to one, that is, unit interval setting.
In this paper, for online unit interval coloring, we conduct a complete analysis of the performance
of their algorithm. Specifically, we prove the number of colors used by their algorithm is at most
3ω(G) − 3. In addition, we present an instance for which the number of colors used by their
algorithm is 3ω(G) − 3. Epstein and Levy [5] showed that the number of colors used by First-Fit
is at most 2ω(G) − 1. That is, our results show that the Kierstead-Trotter algorithm is not optimal
for the unit interval coloring.
Related Results. In online unit interval coloring, the current best upper and lower bounds
are 2ω(G) − 1 and 3ω(G)/2, respectively by Epstein and Levy [5]. Furthermore, Chrobak and
Ślusarek [3] and Epstein and Levy [5] showed that a lower bound on the number of colors used by
First-Fit is 2ω(G) − 1. Hence, the performance of First-Fit for the unit interval case is tightly
analyzed.
1

On the other hand, recent research on online interval coloring has focused on evaluating the
performance of First-Fit [8, 3, 10, 13, 14, 11], which still remains open. The current best upper
and lower bounds are 8ω(G) [13, 14] and 5ω(G) [11] respectively.
Variants of online interval coloring with some constraints and generalizations of that have been
extensively studied as well (see e.g. [1, 12, 5, 2, 6, 4, 14]). In addition, the max coloring problem,
which was proposed by Pemmaraju et al. [14], is a generalization of the vertex coloring problem.
They pointed out that this problem of an interval graph is closely related to the interval coloring
problem, and Epstein and Levy [7] studied the max coloring of interval graphs in an online setting.

2

Kierstead-Trotter algorithm

In this section, we give the definition of the algorithm by Kierstead and Trotter [9], which we
analyze in this paper. First, we give some definitions to define it.
Let vi be the ith interval which is revealed to the online algorithm. The algorithm gives each
interval v the value ℓ(v), called the level of v, and sets its value just before coloring v. The algorithm
colors v based on its level. (Levels are initialized to one at the beginning of the first call of the
algorithm.) Let us define Vx,y (i) = {vj ∈ V | j ≤ i, x ≤ ℓ(vj ) ≤ y}, Ex,y (i) = {(u, v) ∈ E | u, v ∈
Vx,y (i)} and Gx,y (i) = (Vx,y (i), Ex,y (i)). Let Pj denote the set of colors dedicated to the graph
Gj,j (i). That is, Pj ∩ Pj ′ = ∅ if j 6= j ′ . For any interval subgraph H ⊆ G and any interval v in H,
ω(H, v) denotes the size of the maximum clique containing v.
Kierstead-Trotter algorithm
Initialize: For each interval v, set ℓ(v) := 1.
Suppose that the ith interval vi is revealed.
Step 1: Set ℓ(vi ) := arg min{j | ω(G1,j (i), vi ) ≤ j}.
Step 2: Color vi considering only Gℓ(vi ),ℓ(vi ) (i) using First-Fit on the colors of Pℓ(vi ) .

3

Analysis

First, we show an upper bound on the number of colors used by Kierstead-Trotter algorithm. Let
n be the total number of given intervals. The following lemma was shown in Theorem 5 of [9].
Lemma 3.1 First-Fit colors G1,1 (n) using at most one color. Also for any j ≥ 2, First-Fit
colors Gj,j (n) using at most three colors.
Lemma 3.2 First-Fit colors G2,2 (n) using at most two colors.
Proof. We prove by contradiction that for any interval v ∈ V2,2 (n), the number of intervals in
V2,2 (n) which intersect v is at most one.
We assume that v intersects two intervals v ′ and v ′′ (6= v ′ ) ∈ V2,2 (n). Since the lengths of v, v ′ ,
and v ′′ are unique, the left and right endpoints of v are contained in either v ′ or v ′′ . Then, it is
clear that the endpoint which v ′ contains is different from the endpoint which v ′′ contains. That is,
the right (left) endpoint of v is included in a clique whose size is two in G1,2 (n). Thus, no interval
exists in V1,1 (n) which contains the right (left) endpoint of v.
2

On the other hand, v intersects an interval in V1,1 (n) by the definition of the algorithm because
the level of v is two. Then, any unit interval intersecting v certainly contains at least one of the
endpoints of v, which contradicts the above fact.
Theorem 3.3 For any unit interval graph G, the number of colors used by the Kierstead-Trotter
algorithm is at most 3ω(G) − 3.
Proof. By Lemmas 3.1 and 3.2, First-Fit colors G1,1 (n) and G2,2 (n) using at most one color and
at most two colors, respectively. Furthermore, for any j ≥ 3, First-Fit colors Gj,j (n) using at
most three colors. Therefore, 1 + 2 + 3(ω(G) − 2) = 3ω(G) − 3, which completes the proof.
Next, we show a lower bound on the number of colors used by the Kierstead-Trotter algorithm.
Theorem 3.4 There exists an instance which gives a graph G such that the number of colors used
by the Kierstead-Trotter algorithm is 3ω(G) − 3.
Proof. An instance which gives graph G is constructed as follows. Let x ≥ 3 be an integer. For
each i = 1, . . . , x + 2, a unit interval is revealed whose left endpoint is located at (i − 1)(1 − x1 ).
Then, for an interval v which is given when i is even, v is included in a clique whose size is two in
the range [(i − 1)(1 − x1 ), (i − 1)(1 − x1 ) + x1 ] just after v is given. Thus the level of v is two.
Next, for each a = 1, 2, . . ., we define ia = a if a 6= 3, 4, i3 = 4, and i4 = 3. Then, for each
j = 2, . . . , x − 1, in the order of i = i1 , i2 , . . . , ix−j+3 , an interval v ′ whose left endpoint is located
′
at (i − 1)(1 − x1 ) + j−1
x is revealed. Then, v is included in a clique whose size is j + 1 in the range
j−1
1
′
′
[i(1 − x1 ) + j−2
x , i(1 − x ) + x ] just after v is revealed, which means that the level of v is j + 1.
In addition, the first, second, and fourth intervals with level j + 1 have different colors when using
First-Fit, namely, First-Fit uses three colors for level j + 1.
Finally, four intervals whose left endpoints are located at (x+1)(1− x1 )+1+ x1 , (x+1)(1− x1 )+2+ x2 ,
(x + 1)(1 − x1 ) + 1 + x2 and (x + 1)(1 − x1 ) + 2 + x1 are revealed one by one in this order. The levels
of the latter two intervals are two, and First-Fit uses two colors for them.
By the above argument, the maximum level of given intervals is x, that is, the size of the
maximum clique in G is x. Therefore, the total number of colors used by the Kierstead-Trotter
algorithm is 1 + 2 + 3(x − 2) = 3x − 3 = 3ω(G) − 3.

References
[1] U. Adamy and T. Erlebach, “Online coloring of intervals with bandwidth,” In Proc. of the
first international Workshop on Approximation and Online Algorithms, pp. 1–12, 2003.
[2] Y. Azar, A. Fiat, M. Levy and N. S. Narayanaswamy, “An improved algorithm for online
coloring of intervals with bandwidth, ” Theoretical Computer Science, Vol. 363, No. 1, pp.
18–27, 2006.
[3] M. Chrobak and M. Ślusarek, “On some packing problems relating to dynamic storage allocation, ” RAIRO Journal on Information Theory and Applications, Vol. 22, pp. 487–499,
1988.
[4] L. Epstein, T. Erlebach and A. Levin, “Variable sized online interval coloring with bandwidth,”
Algorithmica, Vol. 53, pp. 385–401, 2009.
3

[5] L. Epstein and M. Levy, “Online interval coloring and variants,” In Proc. of the 32nd International Colloquium on Automata, Languages and Programming, pp. 602–613, 2005.
[6] L. Epstein and M. Levy, “Online interval coloring with packing constraints,” Theoretical Computer Science, Vol. 407, No. 1-3, pp. 203–212, 2008.
[7] L. Epstein and M. Levy, “On the max coloring problem,” Theoretical Computer Science, Vol.
462, No. 30, pp. 23–38, 2012.
[8] H. A. Kierstead, “The linearity of first-fit coloring of interval graphs,” SIAM Journal on
Discrete Mathematics, Vol. 1, pp. 526–530, 1988.
[9] H. A. Kierstead and W. T. Trotter, “An extremal problem in recursive combinatorics,” Congressus Numerantium, Vol. 33, pp. 143–153, 1981.
[10] H. A. Kierstead and J. Qin, “Coloring interval graphs with first-fit,” SIAM Journal on Discrete
Mathematics, Vol. 8, pp. 47–57, 1995.
[11] H. A. Kierstead, D. A. Smith and W. T. Trotter, “First-fit coloring on interval graphs has
performance ratio at least 5,” European Journal of Combinatorics, Vol. 51, pp. 236–254, 2016.
[12] N. S. Narayanaswamy, “Dynamic storage allocation and online colouring interval graphs,”
In Proc. of the 10th annual international Conference on Computing and Combinatorics, pp.
329–338, 2004.
[13] N. S. Narayanaswamy and R. S. Babu, “A note on first-fit coloring of interval graphs,” Order,
Vol. 25, No. 1, pp. 49–53, 2008.
[14] S. V. Pemmaraju, R. Raman, and K. Varadarajan, “Max-coloring and online coloring with
bandwidths on interval graphs,” ACM Transactions on Algorithms, Vol. 7, No. 3, pp. 1–21,
2011.

4

