Seminar series
Date
Tue, 29 Apr 2025
Time
14:00 -
15:00
Location
L4
Speaker
Jaroslav Nešetřil
Organisation
Charles University
Graphs (and structures) which have a linear ordering of their vertices with given local properties have a rich spectrum of complexities. Some have full power of class NP (and thus no dichotomy) but for biconnected patterns we get dichotomy. This also displays the importance of Sparse Incomparability Lemma. This is a joint work with Gabor Kun (Budapest).