Three-player Col played on trees isNP-complete
Alessandro Cincotti · 2009
The game of Col is a two-player mapcoloring game invented by Colin Vout where to establish who has a winning strategy on a general graph is a PSPACE-complete problem. However, winning strategies can be found on specific graph instances, e.g., k-ary complete trees. Three-player Col is a threeplayer version of Col. Because of the possibility to form alliances, cooperation between players is a keyfactor to determine the winning coalition and, as a result, three-player Col played on trees is NP-complete.