Packing graphs of bounded codegree

Abstract

Two graphs $G_1$ and $G_2$ on $n$ vertices are said to pack if there exist injective mappings of their vertex sets into $[n]$ such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that, if $({\Delta }_1(G)+1)({\Delta }_2(G)+1)\le n+1$, then $G_1$ and $G_2$ pack. We consider the validity of this assertion under the additional assumption that $G_1$ or $G_2$ has bounded codegree. In particular, we prove for all $t\ge 2$ that, if $G_1$ contains no copy of the complete bipartite graph $K_{2,t}$ and ${\Delta }_1>17t\cdot {\Delta }_2$, then $({\Delta }_1(G)+1)({\Delta }_2(G)+1)\le n+1$ implies that $G_1$ and $G_2$ pack. We also provide a mild improvement if moreover $G_2$ contains no copy of the complete tripartite graph $K_{1,1,s}$, $s\ge 1$.

13 pages, 6 figures