A k-partite graph is a graph whose graph vertices can be partitioned into k disjoint sets so that no two vertices within the same set are adjacent. Determining whether a graph is k-partite for k>=3 is NP-complete.

complete k-partite graph | k-chromatic graph | k-colorable graph