Noon lecture

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

On 28.03.2019 at 12:30 in S6, there is the following noon lecture:

Algorithms for graphs without linear forests

Tereza Klimošová

KAM, MFF, Charles University

Abstract

Many graph problems that are NP-hard in general are solvable on polynomial time when we restrict ourselves to a class of H-free graphs, that is, graphs without an induced copy of a fixed graph H. In my talk I will focus on two such problems - Maximum Weight Independent Set and 3-Colouring. Both problems are known to be NP-hard even for graphs of large girth, thus, one can only hope to find a polynomial time algorithm for H-free graphs when H is a forest.

I will present a polynomial-time algorithm for Maximum Weight Independent Set problem on P6-free graphs, that is, graphs that has no path on 6 vertices as an induced subgraph and a polynomial-time algorithm for 3-Colouring for P2+P5-free graphs and for P3+P4-free graphs, where Pr+Ps is the disjoint union of paths on r and s vertices. The latter result together with previously known results yields complete complexity classification of 3-Colouring on H-free graphs for all graphs H on up to seven vertices.

The talk includes joint results with Andrzej Grzesik, Marcin Pilipczuk and Michał Pilipczuk and with Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma and Veronika Slívová.

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

Webmaster: kamweb.mff.cuni.cz         Modified: 25. 02. 2019