The maximum-average-degree partition conjecture
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.