Toward Żak's conjecture on graph packing (Q286756)

The paper studies the problem of graph packing. Two graphs \(G_1\) and \(G_2\) with the same order \(n\) are said to pack if there is an edge-disjoint placement of them onto the same set of \(n\) vertices. Research on graph packing began in the below two papers, both published in 1978. In [J. Comb. Theory, Ser. B 25, 295--302 (1978; Zbl 0417.05037)], \textit{N. Sauer} and \textit{J. Spencer} proved that if \(|E(G_1)|+|E(G_2)|<\frac{3}{2}n-2\), then \(G_1\) and \(G_2\) pack. \textit{B. Bollobás} and \textit{S. E. Eldridge} [J. Comb. Theory, Ser. B 25, 105--124 (1978; Zbl 0387.05020)] obtained a stronger result that if the maximum degree of \(G_1\) and \(G_2\), \(\Delta(G_1),\Delta(G_2)\leq n-2\), and if \(|E(G_1)|+|E(G_2)|<2n-3\), then \(G_1\) and \(G_2\) pack, with some exception.NEWLINENEWLINE\textit{A. Żak} [SIAM J. Discrete Math. 28, No. 4, 1686--1698 (2014; Zbl 1314.05169)] combined the conditions on the number of edges and maximum degrees together, and obtained a stronger result for large graphs. Let \(G_1\) and \(G_2\) be two graphs of order \(n\geq 10^{10}\). If \(|E(G_1)|+|E(G_2)|+\max\{\Delta(G_1),\Delta(G_2)\}<\frac{5}{2}n-2\), then \(G_1\) and \(G_2\) pack. Furthermore, Żak showed that the bound can be improved if the star on \(n\) vertices is forbidden. Let \(G_1\) and \(G_2\) be two graphs on \(n\) vertices with \(\Delta(G_1),\Delta(G_2)\leq n-2\). If \(|E(G_1)|+|E(G_2)|+\max\{\Delta(G_1), \Delta(G_2)\}<3n-96n^{3/4}-65\), then \(G_1\) and \(G_2\) pack. It is conjectured that the bound on the right side can be improved to \(3n-7\). NEWLINENEWLINENEWLINE In the present paper, the authors verify that Żak's conjecture holds up to the choice of the additive constant. Namely, Let \(C=11(195^2)=418275\). Let \(G_1\) and \(G_2\) be two graphs on \(n\) vertices with \(\Delta(G_1),\Delta(G_2)\leq n-2\). If \(|E(G_1)|+|E(G_2)|+\max\{\Delta(G_1),\Delta(G_2)\}<3n-C\), then \(G_1\) and \(G_2\) pack.NEWLINENEWLINENEWLINEThe proof of the theorem uses the concept of list packing. A graph triple \(\mathcal G=(G_1,G_2,G_3)\) consists of two disjoint graphs \(G_1=(V_1,E_1)\) and \(G_2=(V_2,E_2)\) on \(n\) vertices, and a bipartite graph \(G_3=(V_1\cup V_2, E_3)\) with partite sets \(V_1\) and \(V_2\). A list packing of \(\mathcal G\) is a packing of \(G_1\) and \(G_2\) such that \(uf(u)\notin E_3\) for any \(u\in V_1\). What the authors prove is the list version of the main theorem. Let \(C=11(195^2)=418275\). Let \(n\geq 2\) and \(\mathcal G=(G_1,G_2,G_3)\) be a graph triple with \(|V_1|=|V_2|=n\), \(\Delta(G_1), \Delta(G_2) \leq n-2\) and \(\Delta(G_3) \leq n-1\). If \(|E_1|+|E_2|+|E_3|+\max\{\Delta(G_1), \Delta(G_2)\}+\Delta(G_3)<3n-C\), then \(\mathcal G\) pack.