Yan Zhu

Orthogonal factorizations in graphs are very useful in combinatorial design, network design, circuit layout and so on. All graphs under consideration are simple. Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$ and let $g$ and $f$ be two integer-valued functions defined on $V(G)$ such that $g(x)\leq f(x)$ for all $x\in V(G)$. Then a $(g,f)$-factor of $G$ is a spanning subgraph $F$ of $G$ with $g(x)\leq d_{F}(x)\leq f(x)$ for all $x\inV(F)$. A $(g,f)$-factorization $\mathscr{F}=\{F_1,F_2,\ldots,F_m\}$ of $G$ is a partition of $E(G)$ into edge-disjoint $(g,f)$-factors $F_1,F_2,\ldots,F_m$. A factorization $\mathscr{F}=\{F_1,F_2,\ldots,F_m\}$ of $G$ is called $r$-orthogonal (or orthogonal, when $r=1$) to $H$ if $|E(H)\bigcap E(F_i)|=r, 1\leq i\leq m$.
Alspach posed the following conjecture on orthogonal factorization problems at a combinatorics meeting.

Conjecture. Let $G$ be a $2d$-regular graph, $\mathscr{F}=\{F_1,F_2,\ldots,F_d\}$ be a $2$-factorization of $G$. Then there exists a $d$-matching $M$ of $G$ to which $\textsl{F}$ is orthogonal.

Many people are interested in this problem and have been partly proved the conjecture. There are so many works on orthogonal factorizations and part of them are introduced in this paper.