Bernhart–Kainen conjecture on dispersable regular bipartite graphs

Let GG be a bipartite graph that is kk-regular. Its dispersable book thickness dbt(G)dbt(G) is the minimum number of pages in a dispersable book embedding, and a graph is dispersable when dbt(G)=Δ(G)dbt(G)=\Delta(G), where Δ(G)\Delta(G) is its maximum degree. Bernhart–Kainen conjecture. Every kk-regular bipartite graph GG is dispersable, that is,

dbt(G)=k.dbt(G)=k.

The conjecture is false for k=3k=3 and k=4k=4: the Gray graph has dispersable book thickness four, and the Folkman graph has dispersable book thickness five. It remains disproved as a general statement despite holding for k2k\leq 2.

Sources & referencesView supporting material

Primary source

Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann and Sergey Pupyrev, “On Dispersable Book Embeddings”, arXiv:1803.10030 (2018).

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.