An online presentation of a graph G is an ordering of its vertices
v_1, v_2, ..., v_n so that at the ith time step, v_i is presented along
with edges between v_i and any v_j, j<i. An online
graph coloring algorithm must assign an irrevocable
color to v_i without knowledge of the remainder of the
graph, i.e., it must choose a color based on the subgraph of G
induced by v_1, ..., v_i. A simple algorithm is First-Fit, which colors
each vertex with the first available color.
We present various lower and upper bounds for the performance of First-Fit
on graphs with bounded pathwidth and graphs with bounded treewidth. We
also present a new parameter called ``persistence'': a
graph with pathwidth k has persistence l if every
vertex is contained in at most l vertex sets of the
path decomposition. Although deciding whether a graph has pathwidth k is
FPT (fixed parameter tractable), deciding whether a graph has pathwidth k
and persistence l is W[t]-hard for all t. Deciding whether a graph has
pathwidth k and persistence l=2 (``domino pathwidth problem'') is
W[2]-hard. Therefore it is unlikely there are FPT
algorithms for either of these problems.
These results are from a
recent
unpublished paper by R. Downey and C. McCartin.