Kolorowania większościowe grafów i digrafów – nowe wyniki i możliwe zastosowania Kolorowanie większościowe to takie kolorowanie wierzchołków grafu, w którym co najmniej połowa sąsiadów każdego wierzchołka ma inny kolor niż on sam. Nieco zaskakująco, liczba niezbędnych do tego kolorów jest stała i wynosi 2 dla dowolnego grafu. Zamiast grafów często rozpatruje się digrafy, wówczas interesuje nas proporcja odpowiednio pokolorowanych sąsiadów wychodzących. Tym razem wiemy, że wystarczą 4 kolory. W badaniach, prowadzonych z różnymi współautorami, skupiałem się na różnych uogólnieniach tego problemu i ich hybrydach: Paleta kolorów nie jest wspólna dla wszystkich wierzchołków, ale każdy może mieć własną, niekoniecznie połowa, ale jakaś inna część sąsiadów ma mieć inny kolor, niż dany wierzchołek, krawędzie (i przez to sąsiedzi) mają różną ważność, odsetek sąsiadów w tym samym/różnym kolorze nie jest wspólny, ale zdefiniowany niezależnie dla poszczególnych wierzchołków, graf lub digraf jest nieskończony, kolory nie są znane z góry, ale ujawniane stopniowo (kolorowanie online). To, że udało się nam (albo innym autorom) w poszczególnych przypadkach zdefiniować efektywne algorytmy kolorowania, ma wymiar praktyczny. Jako przykład niech posłuży problem układania programu konferencji z sesjami równoległymi, których może być nawet kilkadziesiąt. Nie da się najczęściej uczestniczyć we wszystkich referatach, które nas interesują. Organizatorzy starają się łączyć referaty o podobnej tematyce, ale to nie musi odzwierciedlać rzeczywistych preferencji uczestników. I tu z pomocą może przyjść kolorowanie większościowe. Uczestnicy to wierzchołki grafu, łuki wskazują preferencje odnośnie do udziału w referatach, zaś kolory to okna czasowe, w których odbywają się sesje. Przykładowo, jeżeli chcemy każdemu uczestnikowi zapewnić możliwość uczestniczenia w 90% referatów, które go interesują (albo symetrycznie: umożliwić udział w jego referacie 90% zainteresowanych), to zawsze można to osiągnąć wykorzystując nie więcej niż 20 okien czasowych. Analizowane przez nas uogólnienia pozwalają na to, aby każdy z uczestników podał listę referatów, które go interesują, przypisał im różne stopnie ważności oraz podał listę okien czasowych, w których może mieć swój referat. Z drugiej zaś strony organizatorzy mogą przypisać różne stopnie ważności do różnych uczestników, a program konferencji może być tworzony na bieżąco, w miarę napływu zgłoszeń.