The maximum-average-degree partition conjecture
Let be a graph, let be positive real numbers, and let denote the maximum average degree of . A partition divides the vertex set into disjoint parts, with and the induced subgraphs on those parts.
Maximum-average-degree partition conjecture. If
then there exists a partition such that
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
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.