Żak's graph-packing conjecture

About 11 years old · traced to

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)≤n−2\Delta(G_1),\Delta(G_2)\leq n-2

and

∣E(G1)∣+∣E(G2)∣+max⁡{Δ(G1),Δ(G2)}≤3n−7,|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 3n−73n-7 replaced by 3n−96n3/4−653n-96n^{3/4}-65, so the conjecture asks for the sharp constant bound; the source provides no resolution.

References

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.