Bernhart–Kainen conjecture on dispersable regular bipartite graphs
Bernhart–Kainen conjecture on dispersable regular bipartite graphs
Let be a bipartite graph that is -regular. Its dispersable book thickness is the minimum number of pages in a dispersable book embedding, and a graph is dispersable when , where is its maximum degree. Bernhart–Kainen conjecture. Every -regular bipartite graph is dispersable, that is,
The conjecture is false for and : 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 .
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
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.