The unlabelled bridge-addable fragment-size conjecture
The unlabelled bridge-addable fragment-size conjecture
Let be a class of graphs that is bridge-addable, meaning that adding an edge between vertices in distinct components preserves membership, and decomposable, meaning that a graph belongs to if and only if each of its components does. For a graph , define its fragment size by
Let be sampled uniformly from the unlabelled graphs in on vertices. Unlabelled bridge-addable fragment-size conjecture. For each such graph class , there is a constant such that, for each positive integer ,
The labelled analogue has a uniform expectation bound, while the source gives an unlabelled example showing that the expectation can grow linearly for a particular class; the conjectured bound remains open in general.
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.