A 
-partite graph is a graph
whose graph vertices can be partitioned into 
disjoint
sets so that no two vertices within the same set are adjacent.
Determining whether a graph is 
-partite for 
is NP-complete (Karp
1972).
k-Partite Graph
See also
Complete k-Partite Graph, k-Chromatic Graph, k-Colorable GraphExplore with Wolfram|Alpha
References
Karp, R. M. "Reducibility Among Combinatorial Problems." In Complexity of Computer Calculations (Ed. R. Miller and J. Thatcher). New York: Plenum, pp. 85-103, 1972.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 12, 1986.Referenced on Wolfram|Alpha
k-Partite GraphCite this as:
Weisstein, Eric W. "k-Partite Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/k-PartiteGraph.html