Marcin Kamiński (Université Libre de Bruxelles, Belgium): Induced packing of odd cycles in a planar graph

Datum objave: 18. 1. 2010
Seminar za teorijo grup in kombinatoriko
Četrtek, 21. 1. 2010, od 17h do 19h, učilnica 016, Pedagoška fakulteta Univerze v Ljubljani

Povzetek: An induced packing of odd cycles in a graph is a packing such that there is no edge in a graph between any two odd cycles in the packing. We prove that the problem is solvable in time 2^{{O}(k^3/2)} \cdot n^3 \lg n when the input graph is planar. We also show that deciding if a graph has an induced packing of two odd cycles is NP-complete. This is joint work with Petr A. Golovach, Daniel Paulusma and Dimitrios M. Thilikos.