The optimal labeling conjecture for bounded twin-width classes
The optimal labeling conjecture for bounded twin-width classes
Let be a graph class, and let an -bits adjacency labeling scheme assign labels of length at most to the vertices of every -vertex graph in , with a fixed decoder determining adjacency from two labels. A class has bounded twin-width if the twin-widths of its graphs are bounded by a constant.
Optimal labeling conjecture. Every bounded twin-width class has a -bits labeling scheme.
The paper presents this as a conjectural improvement of its labeling theorem, aiming for optimality up to the second-order term. No resolution is given in the supplied text.
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.