O większościowym wariancie problemu kolorowania grafu

Kolorowanie większościowe to problem grafowy w którym osłabiamy warunki wymagane w klasycznym problemie kolorowania grafu. Kolorując większościowo rządamy, aby ustalony procent sąsiadów był w innym kolorze niż wierzchołek. W tej pracy skupiamy się na omówieniu różnych wariantów tego problemu i omówimy stan badań nad tematem.

In broad terms, the majority coloring problem is a way to weaken the constraints in a classical coloring problem. We make the requirement for the neighborhood of a given vertex less strict by allowing some of its neighbors to share the color with it, namely for some we allow at most fraction of its neighbor to have the same color. In this thesis, we will focus on different flavors of the majority coloring problem and try to summarise known results.