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á.