Online graph coloring of graphs with bounded pathwidth or bounded
treewidth

 

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.