The maximum-average-degree partition conjecture

About 7 years old · traced to

Let GG be a graph, let c1,c2c_1,c_2 be positive real numbers, and let mad(G)\mathrm{mad}(G) denote the maximum average degree of GG. A partition V(G)=A⊎BV(G)=A\uplus B divides the vertex set into disjoint parts, with G[A]G[A] and G[B]G[B] the induced subgraphs on those parts.

Maximum-average-degree partition conjecture. If

mad(G)<c1+c2,\mathrm{mad}(G)<c_1+c_2,

then there exists a partition V(G)=A⊎BV(G)=A\uplus B such that

mad(G[A])<c1andmad(G[B])<c2.\mathrm{mad}(G[A])<c_1\qquad\text{and}\qquad \mathrm{mad}(G[B])<c_2.

This is recalled in the source as a main open problem concerning partitions that decrease maximum average degree. The preceding corollaries provide special cases and applications, but the general assertion remains open.

References

Primary source

Wojciech Nadara and Marcin Smulewicz, “Decreasing the maximum average degree by deleting an independent set or a d-degenerate subgraph”, arXiv:1909.10701 (2020).

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.