Toward Żak's conjecture on graph packing

Győri, Ervin and Kostochka, A. and McConvey, Andrew and Yager, Derrek (2016) Toward Żak's conjecture on graph packing. JOURNAL OF COMBINATORICS, 7 (2-3). pp. 307-340. ISSN 2156-3527

Preview

Text packing2.pdf Download (440kB) | Preview

Abstract

Two graphs G1=(V1,E1) and G2=(V2,E2), each of order n, pack if there exists a bijection f from V1 onto V2 such that uv∈E1 implies f(u)f(v)∉E2. In 2014, \.{Z}ak proved that if Δ(G1),Δ(G2)≤n−2 and |E1|+|E2|+max{Δ(G1),Δ(G2)}≤3n−96n3/4−65, then G1 and G2 pack. In the same paper, he conjectured that if Δ(G1),Δ(G2)≤n−2, then |E1|+|E2|+max{Δ(G1),Δ(G2)}≤3n−7 is sufficient for G1 and G2 to pack. We prove that, up to an additive constant, \.{Z}ak's conjecture is correct. Namely, there is a constant C such that if Δ(G1),Δ(G2)≤n−2 and |E1|+|E2|+max{Δ(G1),Δ(G2)}≤3n−C, then G1 and G2 pack. In order to facilitate induction, we prove a stronger result on list packing.

Actions (login required)

Edit Item