*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 15th September, 2.15 in Fine Hall 224 Speaker: Matthias Mnich, International Computer Science Institute, Berkeley Title: Domination when the stars are out Abstract: We algorithmize the recent structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that several domination problems are fixed-parameter tractable, and even possess polynomial-sized kernels, on claw-free graphs. To complement these results, we establish these problems are not fixed-parameter tractable on the slightly larger class of graphs that exclude K_{1,4} as an induced subgraph. Our results provide a dichotomy for K_{1,L}-free graphs and show that the problems are fixed-parameter tractable if and only if L ≤ 3. The algorithms we obtain generalize and unify several earlier algorithms for problems on claw-free graphs, and turn the existential decomposition by Chudnovsky and Seymour into an efficient constructive decomposition. (Joint work with Danny Hermelin, Erik Jan van Leeuwen and Gerhard Woeginger.) ----------- Next week: Ron Aharoni Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)