  A subgraph of an edge-coloured graph is called rainbow if all its edges have
distinct colours. The study of rainbow subgraphs goes back more than two
hundred years to the work of Euler on Latin squares and has been the focus of
extensive research ever since. Euler posed a problem equivalent to finding
properly $n$-edge-coloured complete bipartite graphs $K_{n,n}$ which can be
decomposed into rainbow perfect matchings. While there are proper
edge-colourings of $K_{n,n}$ without even a single rainbow perfect matching,
the theme of this paper is to show that with some very weak additional
constraints one can find many disjoint rainbow perfect matchings. In
particular, we prove that if some fraction of the colour classes have at most
$(1-o(1)) n$ edges then one can nearly-decompose the edges of $K_{n,n}$ into
edge-disjoint perfect rainbow matchings. As an application of this, we
establish in a very strong form a conjecture of Akbari and Alipour and
asymptotically prove a conjecture of Barat and Nagy. Both these conjectures
concern rainbow perfect matchings in edge-colourings of $K_{n,n}$ with
quadratically many colours.
  Using our techniques, we also prove a number of results on
near-decompositions of graphs into other rainbow structures like Hamiltonian
cycles and spanning trees. Most notably, we prove that any properly coloured
complete graph can be nearly-decomposed into spanning rainbow trees. This
asymptotically proves the Brualdi-Hollingsworth and Kaneko-Kano-Suzuki
conjectures which predict that a perfect decomposition should exist under the
same assumptions.
