Originators: Daniel Heldt, Kolja Knauer, and Torsten Ueckerdt (presented by Douglas West - REGS 2011)
Definitions: A k-interval representation of a graph G assigns each vertex a set that is the union of at most t intervals on the real line, so that vertices are adjacent if and only if the sets assigned to them intersect. The graphs having such representations with k=1 are the interval graphs. The interval number of a graph G, written i(G), is the minimum k such that G has a k-interval representation.
The track number of G, written t(G), is the minimum number of interval graphs whose union is G. Interval representations of these interval graphs can be viewed as lying on separate "tracks" and together yield a t(G)-interval representation of G. Hence always i(G)≤t(G).
The problem is to show that this inequality can be very bad. If i(G)=1, then t(G)=i(G), but this equality fails when i(G)>1. In particular, if G is a line graph, then i(G)≤2, since G decomposes into complete subgraphs such that each vertex lies in at most two of them.
Problem: ([HKU]) Show that the track number of the line graph of Kn grows with n. How fast?
Comments: In [HKU], it is conjectured that for line graphs the track number is not bounded above by any function of the interval number. Ueckerdt suggested the particular example of L(Kn). REGS students have shown that the track number of L(Kn) is bounded above by a multiple of log n. They also solved the problem by showing that the track number of L(Kn) grows at least as fast as log*n. There remains a large gap between the lower and upper bounds, but the value is now known to grow.
References:
Daniel Heldt, Kolja Knauer, and Torsten Ueckerdt.
Track-number and caterpillar arboricity of graphs of fixed treewidth,
Graph Drawing 2011.