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ą 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 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.
Współautor: Jakub Przybyło.