← All problems

Bernhart–Kainen conjecture on dispersable regular bipartite graphs

8 years old · traced to

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 k≤2k\leq 2.

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

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.