The unlabelled bridge-addable connectivity conjecture
The unlabelled bridge-addable connectivity conjecture
Let be a class of graphs, let be the set of unlabelled graphs in on vertices, and let denote a graph sampled uniformly from . A graph class is bridge-addable if adding an edge between vertices in distinct components preserves membership. Unlabelled bridge-addable connectivity conjecture. There is a such that, if is bridge-addable, then
for each . This asks for a uniform positive lower bound on connectivity in the unlabelled setting; the source notes that little was known about this case and refers to a theorem below that bears on the question.
Sources & referencesView supporting material
Primary source
Colin McDiarmid, “Connectivity for an unlabelled bridge-addable graph class”, arXiv:2001.05256 (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.