Bollobás–Eldridge degree-product packing conjecture

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.