Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Tuesday, May 17, 2022, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Nicolas Grelier

Max clique in disk graphs and Max independent set in graphs with forbidden odd cycles

In this talk, I will present several nice results about maximum clique in disk graphs and related classes. First, I will present a polynomial time algorithm for unit disk graphs discovered by Clark, Colbourn and Johnson (‘90). I will also present an EPTAS for maximum clique in disk graphs as shown by Bonnet et al. (‘17) and Bonamy et al. (‘18).

One of the key ingredients used in the EPTAS is the fact that in disk graphs, the complement of two mutually induced odd cycles is a forbidden subgraph. Similarly, Atminas and Zamaraev (‘16) showed that in unit disk graphs, the complement of an edge and an odd cycle that are mutually induced is a forbidden subgraph. This leads to the study of maximum independent set in graphs where two mutually induced odd cycles, respectively one edge and an odd cycle, are forbidden subgraphs. I will present some results from an ongoing work together with Bonnet, Chakraborty and Thomassé.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login