  A traditional Nordhaus-Gaddum problem for a graph parameter $\beta$ is to
find a (tight) upper or lower bound on the sum or product of $\beta(G)$ and
$\beta(\bar{G})$ (where $\bar{G}$ denotes the complement of $G$). An
$r$-decomposition $G_1,\dots,G_r$ of the complete graph $K_n$ is a partition of
the edges of $K_n$ among $r$ spanning subgraphs $G_1,\dots,G_r$. A traditional
Nordhaus-Gaddum problem can be viewed as the special case for $r=2$ of a more
general $r$-part sum or product Nordhaus-Gaddum type problem. We determine the
values of the $r$-part sum and product upper bounds asymptotically as $n$ goes
to infinity for the parameters tree-width and its variants largeur
d'arborescence, path-width, and proper path-width. We also establish ranges for
the lower bounds for these parameters, and ranges for the upper and lower
bounds of the $r$-part Nordhaus-Gaddum type problems for the parameters
Hadwiger number, the Colin de Verdi\`ere number $\mu$ that is used to
characterize planarity, and its variants $\nu$ and $\xi$.
