University of Primorska
Faculty of Mathematics, Natural Sciences and Information Technologies
Datum / Date: 20.2.23
Čas / Time: 15:00 — 16:00
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Paweł Rzążewski (Warsaw University of Technology and University of Warsaw, Poland)
Naslov / Title: Understanding graphs with no long claws
Povzetek / Abstract:
A classic result of Alekseev asserts that for connected H the Maximum Independent Set (MIS) problem in H-free graphs in NP-hard unless H is a path or a subdivided claw. Recently we have witnessed some great progress in understanding the complexity of MIS in P_t-free graphs. The situation for forbidden subdivided claws is, however, much less understood.
During the talk we will present some recent advances in understanding the structure of graphs with no long induced claws, and their applications in designing algorithms for MIS and related problems.
Everyone is welcome and encouraged to attend.