Bollobás–Eldridge small-size graph packing conjecture

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)nk,|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 k4k\geq 4 and is regarded as a major open problem in graph packing theory.

Sources & referencesView supporting material

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.