Degree Sequence Problem on $k$-Partite Graphs 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.
 A: 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.
A: The problem, as I understand it, is not NP-hard. Assuming that the given partition and degree distribution is feasible, a greedy algorithm will give you a $k$-partite graph.
Here is the idea:
 Notation :


*

*$E(G)$ and $V(G)$ are the edge-set and vertex-set of the graph $G$.

*$e:v - u$ means $e \in E(G)$ if $v \neq u \in V(G)$.

*for $v\in V(G)$, $P(v)$ is the largest set such that $v \in P(v)$ and for $u \not \in P(v)$, $e:v-u \not \in E(G)$ (a parition of vertices).


 Observation : Let $G$ be a simple $k$-partite graph. Then


*

*Swapping the end-points of any two-edges maintains the degree distribution

*If the swap does not introduce self-loops, the simplicity is maintained.

*If the new edges are not within the same partition ,the graph stays $k$-paritite.


 Note: 


*

*Swapping the end-points of edges does not change the number of edges at the corresponding vertices

*If there no self-loops then the graph will be simple.

*Again, by definition $G$ is $k$-partite and we are assuming the swap is not violating the condition.


Now the following algorithm will find you a $k$-partitte graph based on the provided distribution of degrees
 Algorithm :


*

*Let $d = [d_1, d_2, ...., d_n]$ be the degree distribution vector 

*while $\exists \;i$ such that $d[i] > 0$:

*

*Find $j$ such that $d[j] > 0$ and $v_j \not \in P(v_i)$. If no such vertex exists, return FALSE

*Add edge $e:v_i - v_j$ to $E(G)$ and let $d[i] \leftarrow d[i] - 1$ and $d[j] \leftarrow d[j] - 1$ by one.


*return TRUE.


*The algorithm above does not work. It seems to work for the case where the given partition is the smallest.
