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 Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972 (Ed. R. E. Miller and J. W. 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 Resource. https://mathworld.wolfram.com/k-PartiteGraph.html