Toward Żak's conjecture on graph packing

Ervin Győri; Alexandr Kostochka; Andrew McConvey; Derrek Yager

paper

Toward Żak's conjecture on graph packing

arXiv:1508.03672

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) \in / E_{2}$ . In 2014, Żak proved that if $Δ (G_{1}), Δ (G_{2}) \leq n - 2$ and $∣ E_{1} ∣ + ∣ E_{2} ∣ + max {Δ (G_{1}), Δ (G_{2})} \leq 3 n - 96 n^{3/4} - 65$ , then $G_{1}$ and $G_{2}$ pack. In the same paper, he conjectured that if $Δ (G_{1}), Δ (G_{2}) \leq n - 2$ , then $∣ E_{1} ∣ + ∣ E_{2} ∣ + max {Δ (G_{1}), Δ (G_{2})} \leq 3 n - 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 $Δ (G_{1}), Δ (G_{2}) \leq n - 2$ and $∣ E_{1} ∣ + ∣ E_{2} ∣ + max {Δ (G_{1}), Δ (G_{2})} \leq 3 n - C$ , then $G_{1}$ and $G_{2}$ pack. In order to facilitate induction, we prove a stronger result on list packing.

21 pages, 11 figures