Toward Żak’s conjecture on graph packing

Alexandr Kostochka (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.; and Sobolev Institute of Mathematics, Novosibirsk, Russia)

Andrew McConvey (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Derrek Yager (Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Abstract

Two graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$, each of order $n$, pack if there exists a bijection $f$ from $V_{1}$ onto $V_{2}$ such that $uv \in E_{1}$ implies $f(u)f(v) \notin E_{2}$. In 2014, Żak proved that if $\Delta(G_{1}), \Delta(G_{2}) \leq n-2$ and $|E_{1}| + |E_{2}| + \max\{ \Delta(G_{1}), \Delta(G_{2}) \} \leq3n - 96n^{3/4} - 65$, then $G_{1}$ and $G_{2}$ pack. In the same paper, he conjectured that if $\Delta(G_{1}), \Delta(G_{2}) \leq n-2$, then the weaker condition $|E_{1}| + |E_{2}| + \max\{ \Delta (G_{1}), \Delta(G_{2}) \} \leq3n - 7$ is sufficient for $G_{1}$ and $G_{2}$ to pack. We prove that, up to an additive constant, Żak’s conjecture is correct. Namely, there is a constant $C$ such that if $\Delta(G_1),\Delta(G_2) \leq n-2$ and $|E_{1}| + |E_{2}| + \max\{ \Delta(G_{1}), \Delta(G_{2}) \} \leq3n - C$, then $G_{1}$ and $G_{2}$ pack. In order to facilitate induction, we prove a stronger result on list packing.

Keywords

graph packing, maximum degree, edge sum, list coloring

2010 Mathematics Subject Classification

05C35, 05C70

Full Text (PDF format)

Published 23 February 2016