Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Tuesday, April 27, 2021, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Michael Krivelevich (Tel Aviv University)
A classical result of Gallai from the sixties asserts that the vertex set V of every graph G can be partitioned into two parts V_1, V_2, each spanning an induced subgraph with all degrees even. It follows that every n-vertex graph contains an induced subgraph on at least n/2 vertices with even degrees.
What can be said about the odd case? A decades old conjecture suggested that every graph G on n vertices of positive minimum degree contains a subset V_0 of size linear in n, with all degrees in the induced subgraph G[V_0] being odd.
Recently, in a joint work with Asaf Ferber we managed to prove this conjecture. In this talk I will discuss the problem and main ingredients of the proof.
Automatic MiSe System Software Version 1.4803M | admin login