Dear all,
Due to a change in circumstances, the seminar on 28 November has been cancelled.
Best regards, Misha Tyomkyn.
--------------------------
On 2024-11-25 10:33, Mykhaylo Tyomkyn wrote:
Dear all,
There will be a noon seminar this Thursday, 28 November, given by Michał Seweryn. Please find the talk details below.
Best regards, Misha Tyomkyn.
Recent Developments in Graph Minor Theory Michał Seweryn Charles University November 28, 2024, 12:20 in S6
Abstract Graph minor theory, developed by Robertson and Seymour, provides powerful tools for understanding structure of graphs. The main achievements of this theory include (1) proving that the minor relation is a well-quasi-order and (2) showing that the k-Disjoint Paths Problem admits an FPT algorithm. A cornerstone of their work is the Graph Minor Structure Theorem, which, in its simplest form, asserts that L-minor-free graphs are clique sums of "k-near embeddable graphs" for some integer k=k(L). This result has found numerous applications, including in the recent proof of the Clustered Hadwiger's Conjecture.
A key challenge in graph minor theory is determining how the constant k depends on the size of the forbidden minor L, with the goal of showing this dependence is polynomial. In this talk, we report on the latest developments in addressing this challenge.
Joint work with Maximilian Gorsky and Sebastian Wiederrecht.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz