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
14.01.2026 Paweł Pękała AGH
Większościowe kolorowania krawędzi grafów
\(\quad\)Większościowym kolorowaniem krawędzi grafu \(G\) nazywamy kolorowanie krawędzi tego grafu takie, że dla każdego wierzchołka grafu \(G\) co najwyżej połowa krawędzi incydentnych z tym wierzchołkiem ma taki sam kolor. Naturalnym uogólnieniem tego problemu są \(\frac{1}{k}\)-większościowe kolorowania krawędzi. W tym wariancie problemu, dla ustalonej liczby naturalnej \(k\), chcemy znaleźć takie kolorowanie krawędzi grafu, że dla każdego wierzchołka co najwyżej \(\frac{1}{k}\)-ta krawędzi z nim incydentnych ma taki sam kolor. W referacie pokażemy ograniczenia na minimalny stopień grafu, który gwarantuje istnienie 1/k-większościowych kolorowań krawędzi za pomocą \(k+1\) kolorów. Rozważymy także wersję listową tego problemu. \(\quad\)Współautor: Jakub Przybyło.
Zespół prowadzący