The optimal labeling conjecture for bounded twin-width classes

Let C\mathcal C be a graph class, and let an f(n)f(n)-bits adjacency labeling scheme assign labels of length at most f(n)f(n) to the vertices of every nn-vertex graph in C\mathcal C, 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 (1+o(1))logn(1+o(1))\log n-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

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.