Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 29.10.2009 at 12:20 in corridor, there is the following noon lecture:

Finding induced paths in claw-free graphs

Jiri Fiala

Abstract

joint work with M. Kaminski, B. Lidicky, and D. Paulusma

We show that for a fixed number of terminals, it is possible to find in a polynomial time an induced path in a claw-free graph that passes through the given set of terminals. The core part of the proof is based on a structural characterization of quasi-line graphs by Chudnovsky and Seymour.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010