All times are given in GMT+2 zone (CET, Warsaw time zone). Scroll down for the detailed program.
Wednesday, June 23rd
Thursday, June 24th
Friday, June 25th
|10.15-11.45||Dieter Kratsch in memoriam|
The conference takes place on Airmeet platform and can be accessed below.
Graph Product Structure Theory
This talk will introduce product structure theorem [Dujmović, Joret, Micek, Morin, Ueckerdt and Wood 2019] that states that every planar graph is contained in the strong product of a bounded treewidth graph and a path. The theorem can be generalized from planar graphs to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs. This introductory talk will also discuss some applications including: asymptotically optimal results for queue number [Heath, Leighton, Rosenberg 1992], and nonrepetitive chromatic number [Alon, Grytczuk, Hałuszczak, and Riordan 2002].
On a method of enumerating independent sets
In this talk, we will present an elementary, yet quite powerful, method of enumerating independent sets in graphs. This method was first employed almost fourty years ago by Kleitman and Winston. It has subsequently been rediscovered and used numerous times by many researchers in various contexts. Our presentation will be illustrated with several applications of it to ‘real-life’ combinatorial problems.
The twin-width of a graph, and more generally of a binary structure, has recently been introduced. It is based on a succession of vertex contractions going from the initial graph to a single vertex, called contraction sequence. Surprisingly many classes have bounded twin-width, while generic classes of bounded twin-width enjoy several structural properties and improved algorithms. Throughout applications in algorithmic and structural graph theory, combinatorics, finite model theory, and algebra, we will survey various uses of twin-width. We wish to demonstrate that, perhaps in hindsight, the notion naturally pops up in many contexts. Among other things, we will see that twin-width behaves well with respect to model theory, is a key concept to handle ordered graphs, and that all the principal width measures can be expressed in terms of contraction sequences. We will propose several open questions.
Chair: Łukasz Kowalik
Chair: Jan Arne Telle
Chair: Saket Saurabh
Chair: Bartosz Walczak
Chair: Bart Jansen
Dieter Kratsch in memoriam
Friday, 10.15 – 11:45