Group coloring is Pi_2^P-complete

Abstract

We prove that computing the group chromatic number of graphs is complete for the class at the second level of the polynomial hierarchy.

Keywords

• Group
• coloring
• Pi_2^P-complete