Smallness characterisation conjecture for graph classes by twin-width

Let C\mathcal{C} be a class of graphs closed under induced subgraphs. Call C\mathcal{C} small if there is a constant cc such that, for every nn, it contains at most n!cnn!\,c^n graphs on vertex set {1,,n}\{1,\dots,n\}. Smallness characterisation conjecture. The class C\mathcal{C} is small if and only if it has bounded twin-width. This would characterise bounded twin-width among hereditary graph classes and extend the corresponding growth dichotomy for matrices; the source gives no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Édouard Bonnet, Colin Geniet, Romain Tessera and Stéphan Thomassé, “Twin-width VII: groups”, arXiv:2204.12330 (2022).

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.