K-partite graph

From Algowiki
Jump to: navigation, search

Definition

An undirected graph [math]G=(V,E)[/math] is called k-partite, if there is a partition of [math]V[/math], hereinafter referred to as [math]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]V_{i}[/math]. In other words, the following implication must hold:

[math]\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]k=2[/math], [math]G[/math] is called bipartite graph.