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
07.10.2026 Jakub Żuchowski PW
Listowe kolorowanie grafów uporządkowanych z zabronionymi podgrafami indukowanymi, c.d.
\(\quad\)Kontynuujemy rozważania na temat problemu listowego kolorowania w klasach grafów uporządkowanych z wykluczonym ustalonym podgrafem indukowanym. Tym razem skupimy się na problemie List-3-Coloring w przypadku, gdy wykluczony wzorzec składa się z dwóch krzyżujących się krawędzi oraz ewentualnych wierzchołków izolowanych. Przedstawimy algorytm quasi-wielomianowy dla tej klasy. Omówimy także związek rozważanej klasy z grafami outerstring. Wyniki uzyskane we współpracy z Pawłem Rafałem Bielińskim, Michałem Dębskim, Martą Piecyk i Pawłem Rzążewskim.
Zespół prowadzący