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).
See also
Complete k-Partite Graph, k-Chromatic Graph, k-Colorable Graph
Explore 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
Cite this as:
Weisstein, Eric W. "k-Partite Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/k-PartiteGraph.html