The small conjecture for hereditary graph classes

Let a graph class be small if the number of its labeled graphs on vertex set [n][n] is at most n!cnn!c^n for some constant cc, and let a graph class be hereditary if it is closed under taking induced subgraphs. A class has bounded twin-width if there is an integer dd such that every graph in the class has twin-width at most dd.

Small conjecture. Every small hereditary class has bounded twin-width.

The conjecture is presented as a converse to the theorem that every class with bounded twin-width is small. The paper does not answer the question, but gives evidence by proving bounded twin-width for many potential counterexamples.

Sources & referencesView supporting material

Primary source

Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant, “Twin-width II: small classes”, arXiv:2006.09877 (2020).

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.