Smallness characterisation conjecture for graph classes by twin-width
Smallness characterisation conjecture for graph classes by twin-width
Let be a class of graphs closed under induced subgraphs. Call small if there is a constant such that, for every , it contains at most graphs on vertex set . Smallness characterisation conjecture. The class 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
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.