The small conjecture for hereditary graph classes
The small conjecture for hereditary graph classes
Let a graph class be small if the number of its labeled graphs on vertex set is at most for some constant , 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 such that every graph in the class has twin-width at most .
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
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.