Quadratic average-degree conjecture for contractible edges
Quadratic average-degree conjecture for contractible edges
An edge of a -connected graph is -contractible if contracting leaves a -connected graph. The average degree is the average of the vertex degrees.
Quadratic average-degree conjecture. There exists a constant such that every finite -connected graph of average degree at least admits a -contractible edge.
Known bounds give an upper bound of order for the relevant average degree, while examples show a quadratic lower-order scale, so the conjecture asks whether the logarithmic factor can be removed. The source gives no resolution evidence.
Sources & referencesView supporting material
Primary source
Matthias Kriesell, “Minimal Connectivity”, arXiv:1101.2357 (2011).
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.