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).

Last updated on 25 Apr 2025, 1:40pm. Please contact us with feedback and comments about this page.