
In a dispersable book embedding, the vertices of a given graph $G$ must be ordered along a line l, called spine, and the edges of G must be drawn at different half-planes bounded by l, called pages of the book, such that: (i) no two edges of the same page cross, and (ii) the graphs induced by the edges of each page are 1-regular. The minimum number of pages needed by any dispersable book embedding of $G$ is referred to as the dispersable book thickness $dbt(G)$ of $G$. Graph $G$ is called dispersable if $dbt(G) = Δ(G)$ holds (note that $Δ(G) \leq dbt(G)$ always holds). Back in 1979, Bernhart and Kainen conjectured that any $k$-regular bipartite graph $G$ is dispersable, i.e., $dbt(G)=k$. In this paper, we disprove this conjecture for the cases $k=3$ (with a computer-aided proof), and $k=4$ (with a purely combinatorial proof). In particular, we show that the Gray graph, which is 3-regular and bipartite, has dispersable book thickness four, while the Folkman graph, which is 4-regular and bipartite, has dispersable book thickness five. On the positive side, we prove that 3-connected 3-regular bipartite planar graphs are dispersable, and conjecture that this property holds, even if 3-connectivity is relaxed.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
