Tight lower bounds for the complexity of multicoloring

Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk +2

In the multicoloring problem, also known as ($a$:$b$)-coloring or $b$-fold coloring, we are given a graph G and a set of $a$ colors, and the task is to assign a subset of $b$ color…