On-Line Coloring of [Unit] Interval Graphs (2009)

Originators:    (presented by A. Kostochka - REGS 2009)

Definitions: In on-line coloring, the vertices of a graph are presented one by one, with the algorithm required to give each a color when it is seen, different from the colors on its earlier neighbors. The on-line chromatic number of a graph G is the least k such that an on-line algorithm exists that guarantees coloring G with at most k colors.

Background: The simple greedy algorithm (also called "First-Fit") produces an on-line coloring of any graph G using at most Δ(G)+1 colors, and better cannot be guaranteed even for trees. For other classes of graphs, especially perfect graphs (where the chromatic number equals the clique number), we seek a bound on the on-line chromatic number in terms of the clique number (the clique number is the maximum number of pairwise-adjacent vertices).

A graph is an interval graph if it is representable by assigning each vertex an interval on the real line so that vertices are adjacent if and only if the corresponding intervals exist. It is a unit interval graph if there is such a representation in which the intervals all have the same length.

Problem: Determine the best possible upper bound on the on-line chromatic number for interval graphs and for unit interval graphs in terms of the clique number. The graphs are presented by presenting intervals in a representation.

Comments: Let ƒ(k) and &fnof'(k) denote the largest on-line chromatic number of interval graphs and of unit interval graphs with clique number k, respectively. Gyárfás and Lehel [GL] showed that the greedy algorithm produces an upper bound. Successive improvements brought the upper bound to c(ε)k1+ε [Wi], then 40k [K], then 25.72k [KQ], and now 8k [NS]. An early lower bound of about 3.56k by [Wo] was improved to 4k in [CS], which also claimed 4.4k without proof. Thus the upper bound is now at most twice the lower bound.

For the more restrictive problem of unit interval graphs, an easy algorithm produces an on-line coloring with at most 2k colors. When an interval is presented with left endpoint x, use a color in {1,...,k} if ⌊x⌋ is odd, and use a color in {k+1,...,2k} if ⌊x⌋ is even. Since the vertices whose left endpoints have a fixed value of ⌊x⌋ form a clique, intersecting intervals will receive distinct colors. Note that this algorithm requires knowing the clique number in advance, but not the graph.

There is a lower bound that presents a unit interval representation requiring at least 3k/2 colors, so 3k/2≤ƒ'(G)≤2k.

References:
[CS] M. Chrobak\en and Ślusarek, On some packing problems related to dynamic storage allocation. RAIRO Inform. Théor. Appl. 22 (1988), no. 4, 487--499.
[K] Kierstead, H. A. The linearity of first-fit coloring of interval graphs. SIAM J. Discrete Math. 1 (1988), no. 4, 526--530.
[KQ] Kierstead, H.A., Qin, J.: Coloring interval graphs with first-fit. Discrete Math. 144, 47--57 (1995)
[NS] Narayanaswamy, N. S.; Subhash Babu, R. A note on first-fit coloring of interval graphs. Order 25 (2008), no. 1, 49--53.
[Wi] Witsenhausen, H. S. On Woodall's interval problem. J. Combinatorial Theory Ser. A 21 (1976), no. 2, 222--229.
Woodall, D. R.; unpublished. ([K] proved the conjecture of Woodall in Combinatorics (Aberystwyth, 1973), p. 202, Problem No. 4, Cambridge Univ. Press, London, 1974.