Żak's graph-packing conjecture

Let G1G_1 and G2G_2 be graphs on nn vertices, and let E(Gi)E(G_i) and Δ(Gi)\Delta(G_i) denote the edge set and maximum degree of GiG_i, respectively. Two graphs pack if there is a bijection between their vertex sets that maps every edge of G1G_1 to a non-edge of G2G_2. Żak's graph-packing conjecture. If

Δ(G1),Δ(G2)n2\Delta(G_1),\Delta(G_2)\leq n-2

and

E(G1)+E(G2)+max{Δ(G1),Δ(G2)}3n7,|E(G_1)|+|E(G_2)|+\max\{\Delta(G_1),\Delta(G_2)\}\leq 3n-7,

then G1G_1 and G2G_2 pack. Żak's preceding theorem proves the same sufficient condition with 3n73n-7 replaced by 3n96n3/4653n-96n^{3/4}-65, so the conjecture asks for the sharp constant bound; the source provides no resolution.

Sources & referencesView supporting material

Primary source

Ervin Győri, Alexandr Kostochka, Andrew McConvey and Derrek Yager, “Toward Żak's conjecture on graph packing”, arXiv:1508.03672 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.