Bollobás–Eldridge degree-product packing conjecture

About 8 years old · traced to

Let H1H_1 and H2H_2 be graphs, let KnK_n be the complete graph on nn vertices, and write Δ(Hi)\Delta(H_i) for the maximum degree of HiH_i. A packing of (H1,H2)(H_1,H_2) in KnK_n is a pair of injections into KnK_n whose induced edge sets are disjoint. Bollobás–Eldridge degree-product conjecture. If

(Δ(H1)+1)(Δ(H2)+1)≤n+1,(\Delta(H_1)+1)(\Delta(H_2)+1)\leq n+1,

then (H1,H2)(H_1,H_2) pack into KnK_n. The paper presents this as an important conjecture concerning packing two graphs under a maximum-degree condition; no resolution status is supplied in the stated context.

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.