On the complexity of three-player snort played on complete graphs
Alessandro Cincotti · 2009
Snort is a map-coloring game invented by Simon Norton where to establish who has a winning strategy on a general graph is a PSPACE-complete problem. Three-player snort is a three-player version of snort where cooperation between players is a key-factor to determine the winning coalition. In this paper, we show that three-player snort played on complete graphs, that is extremely easy to solve in normal play convention, becomes an NP-complete problem in misegravere play convention.