Bollobás–Eldridge small-size graph packing conjecture

About 8 years old · traced to

Let H1,H2,…,HkH_1,H_2,\ldots,H_k be graphs and let KnK_n be the complete graph on nn vertices. A packing of (H1,H2,…,Hk)(H_1,H_2,\ldots,H_k) in KnK_n is a collection of injections of the graphs into KnK_n whose induced edge sets are pairwise disjoint. Bollobás–Eldridge packing conjecture. If

∣E(H1)∣,∣E(H2)∣,…,∣E(Hk)∣≤n−k,|E(H_1)|,|E(H_2)|,\ldots,|E(H_k)|\leq n-k,

then (H1,H2,…,Hk)(H_1,H_2,\ldots,H_k) pack in KnK_n. The conjecture is known for k=2k=2 and k=3k=3, but remains open for k≥4k\geq 4 and is regarded as a major open problem in graph packing theory.

References

Primary source

Alice Joffard and Hamamache Kheddouci, “Labeled Packing of Cycles and Circuits”, arXiv:1805.06171 (2018).

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.