  Analyzing pseudo-telepathy graph games, we propose a way to build
contextuality scenarios exhibiting the quantum supremacy using graph states. We
consider the combinatorial structures that generate equivalent scenarios. We
introduce a new tool called multipartiteness width to investigate which
scenarios are harder to decompose and show that there exist graphs generating
scenarios with a linear multipartiteness width.
