The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees of the nodes are $D = (d\_1, d\_2, ..., d\_n)$.


From the Erdős–Gallai theorem it follows that such a graph can be found in polynomial time.
With some minor modifications it is also possible to ask for a simple undirected bi-partite graph for which it holds that the degrees of the nodes are $D\_1 = (d\_{1\_1}, d\_{1\_2}, ..., d\_{1\_n})$ resp. $D\_2 = (d\_{2\_1}, d\_{2\_2}, ..., d\_{2\_n})$.


I am interested in a more general case where the graph in question is a k-partite graph and the sets $D\_1, D\_2, ... D\_k$ are given.


Is anybody aware of any results on that? 
I would suspect the problem to be NP-Hard but i don't (yet) have any proof.



Degree Sequence Problem on $k$-Partite Graphs
The problem a hand can be modeled as a restricted degree sequence problem as explained in that paper: <http://arxiv.org/pdf/1301.7523v3.pdf>


Or as a Degree Sequence Problem with Associated Costs as in <http://research.microsoft.com/en-us/um/people/nvishno/site/publications_files/mvdeg02.pdf>


Unfortunately, both problems require finding a perfect matching on a graph with $\mathcal{O}(n^2)$ nodes which is impractical.


