It is well known that a graph is said to be $k$-partite if its vertex set can be partitioned in to k non empty sets such that no two vertices in the same set are adjacent.
My question is whether such a '$k$' must be minimum ? ; but the definition doesn't have such a condition explicitly.
A reason for this question is as follows: If we do not assume this condition, then every graph on $k $ vertices is $k$-partite, with all the singleton subsets of its vertex set as the partitions. Likewise, the totally disconnected graph on $k$ vertices ( i.e the graph on $k$ vertices having no edges) can be viewed as a r- partite graph for each $1 \leq r \leq k$.
$\endgroup$2 Answers
$\begingroup$It is less restrictive the larger $k$ gets, so less interesting, but it is true. Given a bipartite graph, you can arbitrarily split one of the parts in two and make a $3-$partite graph. If you prove a theorem about $3-$partite graphs it will apply to bipartite graphs (at least those with at least $3$ vertices).
$\endgroup$ 2 $\begingroup$No it does not, for example, every bipartite graph is also $5$-partite.
$\endgroup$ 2
