Mariusz Meszka (AGH University of Science and Technology, Kraków, Poland) Orthogonal onefactorizations\\ of complete multipartite graphs Abstract: A onefactor of a graph $G$ is a regular spanning subgraph of degree one. A onefactorization of $G$ is a set ${\cal F}=\{F_1,\,F_2,\ldots ,F_r\}$ of edgedisjoint onefactors such that $E(G)=\bigcup_{i=1}^r E(F_i)$. Two onefactorizations ${\cal F}=\{F_1,\,F_2,\ldots ,F_r\}$ and ${\cal F'}=\{F'_1,\,F'_2,\ldots ,F'_r\}$ are orthogonal if $F_i\cap F'_j\leq 1$ for all $1\leq i < j \leq r$. A set of $k$ onefactorizations $\{{\cal F}^1,{\cal F}^2,\ldots ,{\cal F}^k\}$ of $G$ is mutually orthogonal if, for every $1\leq i < j\leq k$, ${\cal F}^i$ and ${\cal F}^j$ are orthogonal. A pair of orthogonal onefactorizations of an $s$regular graph $G$ on $2n$ vertices corresponds to the existence of a Howell design of type $(s,2n)$, for which a graph $G$ is called an underlying graph. Let $S$ be a set of $2n$ symbols. A Howell design $H(s,2n)$ on the symbol set $S$ is an $s\times s$ array that satisfies the following conditions: (1) every cell is either empty or contains an unordered pair of symbols from $S$, (2) every symbol of $S$ occurs exactly once in each row and exactly once in each column of $H$, (3) every unordered pair of symbols occurs in at most one cell of $H$. Necessary condition for the existence of Howell designs $H(s,2n)$ is $n\leq s\leq 2n1$. A pair of orthogonal onefactorizations of a complete bipartite graph $K_{n,n}$ corresponds to a Howell design $H_k(n,2n)$, and moreover they are equivalent to a pair of mutually orthogonal latin squares of side $n$. In the other extreme case, an $H(2n1,2n)$ is a Room square of side $2n1$, which corresponds to two orthogonal onefactorizations of a complete graph $K_n$. An important question related to Howell designs concerns properties of graphs which are underlying graphs of Howell designs. While for $s=2n1$ and $s=2n2$ these graphs are unique (the complete graph $K_{2n}$ and the cocktail party graph $K_{2n}\setminus F$, respectively, where $F$ is a onefactor), determining these graphs in general seems to be hopeless. The goal of this talk is to show that balanced complete multipartite graphs are underlying graphs of Howell designs. The main result provides almost complete solution to the existence problem of two orthogonal onefactorizations of a complete balanced multipartite graph $K_{p\times q}$. Some infinite families of $k$ mutually orthogonal onefactorizations of $K_{p\times q}$ for $k\geq 3$ will be also presented. 
