In that case, the comment above is wrong. Also, given this example, it might seem easy that if we could find the min $k$ for $k$-partite graph then we could draw it. But that won't work either and finding min. $k$ is I guess NP-hard (vertex coloring reduction).

You are right about the algorithm returning false. But the problem is that the degree distribution you provided, relates to a bi-partite graph, not a 3-partite, unless I got it wrong again. Did you mean a grpah like this: $v_i, i \in \{1, 2, 3, 4, 5, 6\}$ where $P(v_1) = \{v_1, v_2\}, P(v_3) = \{v_3, v_4\}, P(v_5) = \{v_5, v_6\}$? In such a case, the only graphs satisfying this [that I could think of] seem to be isomorphic to this: $e_1: v_1 - v_3, e_2:v_2 - v_6, e_3: v_4-v_5$. In such a case though, the graph is actually bi-partite.