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 .
References
Status
- Refuted: Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, and Sergey Pupyrev. On Dispersable Book Embeddings (Graph Drawing and Network Visualization 2018, Lecture Notes in Computer Science, Springer, 2018) https://doi.org/10.1007/978-3-030-00256-5_1
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
No solutions have been posted yet.