Tri Partite |
|
A graph $G=(V,E)$ is tri-partite if the vertex set $V$ can be partitioned into three sets $V_0$, $V_1$, and $V_2$, such that $V_i$ has no edges. In other words, all the edges of $G$ run between the $V_i$ and not within, so $V_i^2 \cap E = \{\}$.
A graph is 3-colourable iff it is tri-partite.
See also: bi-partite.