K-partite graph

Definition

An undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called k-partite, if there is a partition of [math]\displaystyle{ V }[/math], hereinafter referred to as [math]\displaystyle{ V=\dot\cup_{i=1}^k V_{i} }[/math], such that there is no edge between two nodes that belong to the same partition component [math]\displaystyle{ V_{i} }[/math]. In other words, the following implication must hold:

[math]\displaystyle{ \forall i\in \{1,\ldots,k\}: v \in V_i \wedge w \in V_i \rightarrow \{v,w\} \not\in E }[/math].

Remark

For [math]\displaystyle{ k=2 }[/math], [math]\displaystyle{ G }[/math] is called bipartite graph.