Quadratic average-degree conjecture for contractible edges

An edge ee of a kk-connected graph is kk-contractible if contracting ee leaves a kk-connected graph. The average degree is the average of the vertex degrees.

Quadratic average-degree conjecture. There exists a constant cc such that every finite kk-connected graph of average degree at least ck2c k^2 admits a kk-contractible edge.

Known bounds give an upper bound of order k2logkk^2\log k 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

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.