On-Line Partitioning of Proper Interval Graphs
Click the Poster to View Full Screen, Right click to save image
Hannah Malko
College:
The Dorothy and George Hennings College of Science, Mathematics, and Technology
Major:
Mathematical Sciences
Faculty Research Advisor(s):
Israel Curbelo
Abstract:
The on-line coloring of interval graphs, in which intervals are drawn on the real line and cannot share a color if intersecting, is the problem of finding the most efficient algorithm for allocating data. It can be represented as a two-person game played by Alice, who presents intervals, and Bob, who colors those intervals arbitrarily. For the presented problem, once an interval is drawn by Alice, it must be colored by Bob before the next interval is presented. Once a color is designated it cannot be changed. Alice’s goal is to force as many colors as possible, while Bob attempts to minimize the number of colors used. The number of intervals that can intersect at a given point on the graph is denoted by the letter w. We consider the problem restricted to proper intervals, meaning intervals of any length may be presented but no interval can be contained by another. For on-line coloring of proper interval graphs, the upperbound is 2w-1 (Chrobak & Slusarek, 1981) and the lower bound is 32w (Epstein & Levy, 2005; Biro & Curbelo, 2023). For over 40 years, the problem remained open for w>3. We solve the problem for w=4.