Seminarium Kombinatoryka, Teoria Grafów i Zbiorów Uporządkowanych
Wydział Matematyki i Nauk Informacyjnych, Politechnika Warszawska
Kalendarz Środy, 10:15-11:45
Pinezka Gmach MiNI PW, Sala 431, ul. Koszykowa 75, Warszawa
Komputer Seminaria odbywają się stacjonarnie z transmisją na platformie MS Teams.
Mail Jeśli chcesz dołączyć do spotkania, to napisz do sekretarza seminarium.

Najbliższy referat
15.04.2026 Martin Milanič University of Primorska
Inverting Ramsey: awesome graph parameters
\(\quad\)We investigate connections between two lines of research related to independent sets and cliques in graphs. One of them studies independence variants of graph parameters such as treewidth or degeneracy. The second line deals with graph classes where some parameters are bounded by a function of the clique number. A famous example is given by the family of χ-bounded graph classes, where the chromatic number is bounded by a function of the clique number. A Ramsey-type argument implies that a graph parameter is bounded by a function of the clique number in any graph class in which the independence variant of the parameter is bounded by a constant. If the reverse implication also holds, we say that the parameter is awesome; otherwise, it is awful. We identify a number of awesome and awful graph parameters, derive some algorithmic applications of awesomeness, and propose a number of open problems related to these notions. This is joint work with Kenny Bešter Štorgel (FIŠ Novo mesto and Primorska), Clément Dallard (Fribourg), Vadim Lozin (Warwick), and Viktor Zamaraev (Liverpool).
Zespół prowadzący