Conjecture on partitioning a dense graph into two dense spanning subgraphs

Let s,t0s,t\geq 0 be real numbers, and let GG be a non-null graph. A subgraph is ss-dense if it has at least ss edges per vertex.

Partition conjecture. If

e(G)(s+t+1)v(G),e(G)\geq (s+t+1)v(G),

then there exist vertex-disjoint non-null subgraphs G1G_1 and G2G_2 such that

e(G1)sv(G1),e(G2)tv(G2),e(G_1)\geq sv(G_1),\qquad e(G_2)\geq tv(G_2),

and

V(G1)V(G2)=V(G).V(G_1)\cup V(G_2)=V(G).

The conjecture would strengthen several aspects of the paper's main theorem and implies another conjecture in the paper. The supplied text records partial results when s=ts=t or when e(G)(s+t+32)v(G)e(G)\geq(s+t+\frac32)v(G), but does not state a complete resolution.

Sources & referencesView supporting material

Primary source

Endre Csóka, Irene Lo, Sergey Norin, Hehui Wu and Liana Yepremyan, “The extremal function for disconnected minors”, arXiv:1509.01185 (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.