The online graph bandwidth problem

The online graph bandwidth problem is defined, and we present an online algorithm that always outputs a (((2k − 1)n + 1)/2k)-bandwidth function for any n-vertex graph with bandwidth k. A lower bound of (k/(k + 1))n − 2 is shown for any such algorithm. Two other protocols for online problems are given, and we prove lower bounds for the bandwidth problem under both of these alternative protocols.