CURRENT  RESEARCH  PROBLEMS

## First Fit Coloring of Interval Graphs

Here's an apparently elementary problem which has a rich history and has produced some really interesting combinatorial mathematics.  Define  FF(k)  to be the largest integer  t  for which there exists an interval graph  G  and a linear order  L  on the vertices of  G  so that:  (1)  the maximum clique size of  G  is  k,  and (2)  First Fit uses  t  colors on  G  when the vertices are processed in the order specified by  L.   In 1976,  Woodall showed that  FF(k)  =  O(k log k).  In 1988, Kierstead showed that  FF(k)  <=  40k,  i.e.,  FF(k)  is linear in  k.  Kierstead and Qin improved this in 1995 to  FF(k)  <=  25.8k.   From below, it follows from our work on on-line coloring of interval graphs that there exists an  e > 0  so that  FF(k) > (3 + e)k   when  k  is large.   In 1990, Chrobak and Slusarek proved that  FF(k)  >  4k - 10  when  k > 6, and they later improved the lower bound to  4.4k.

In 2003, Pemmaraju, Raman and Varadarajan made a major breakthrough by showing that  FF(k) <= 10k and commented that their upper bound might be improved but that the technique wouldn't yield a result better than  8k.  Later in 2003, their predictions were confirmed, and their technique was refined by Brightwell, Kierstead and Trotter to obtain an upper bound of  8k. In 2004, Narayansamy and Babu found an even cleaner argument for this bound that actually  yields the slightly stronger result:  FF(k) <=  8k - 3.

Later in 2004, Kierstead and Trotter improved the lower bound by showing that for every  e > 0,  FF(k) > (5 - e)k  when  k  is sufficiently large.  Most recently, Kierstead and Trotter have shown that the tree-like structures used by various authors to obtain lower bounds cannot yield a better performance ratio than  5.   So  as  k  goes to infinity, the ratio  FF(k)/k  tends to a limit that is somewhere between  5  and  8,   and I will bet that  5  is the right answer.

## Hamiltonian Path and Cycle Problems

Lately, I have been taking a fresh look at two old problems.  The first one is the notorious "middle two levels" problem.   Let  n = 2k+1  be an odd integer and consider the subset lattice consisting of all subsets of  {1, 2, ..., n}.  The middle two levels consisting of the sets of size  k  and  k+1  form a bipartite graph, and it is conjectured that this graph is hamiltonian.  Known to be true for  n  at most  15.  The origins of this problem are not completely clear, but it was first posed to me by Ivan Havel in the summer of 1982.  Havel in fact showed me a reprint in which the problem was posed.

The second problem is not as well known but seems similar in spirit.  Felsner and I conjectured that for all  n, there is a listing S_1, S_2, ..., S_t  (where t  = 2^n) of all subsets of  {1, 2, ..., n}  so that (1)  S_2  is not a subset of  S_1, and (2) for all  i  with 1 <  t-1, S_{i+1  is not a subset of the union of  S_i  and  S_{i-1}.  Unlike the first problem, the origin of this one is completely clear.  It comes from efforts to determine the maximum chromatic number of the diagram of an interval order of given height.  There are some interesting partial results on this problem, and one of their consequences is a construction which gives a cycle in the middle two levels which is a positive fraction of the maximum possible size.  This is a neat problem.