Journal of Combinatorics

Volume 7 (2016)

Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

Toward Żak’s conjecture on graph packing

Pages: 307 – 340

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a6

Authors

Ervin Gyori (Alfréd Rényi Institute of Mathematics, Budapest, Hungary; and Department of Mathematics, Central European University, Budapest, Hungary)

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

Published 23 February 2016