The maximum-average-degree partition conjecture

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)=ABV(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)=ABV(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.

Sources & referencesView supporting material

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.