15 problems

Let $G$ be a regular bipartite graph, let $\Delta(G)$ denote its maximum degree, and let $mbt(G)$ denote its maximum book thickness. Bernhart–Kainen conjecture. One has … This conj…

Let $G$ be a graph, and let $mnl(G)$ denote the minimum number of links among spatial embeddings of $G$. A book embedding is a spatial embedding in which the graph is embedded with…

Let $G_0=K_3$. For $k\geq1$, let $G_k$ be the planar $3$-tree obtained by adding a $3$-simplicial vertex onto the vertex set of each face of $G_{k-1}$. Let…

Let ${\mathcal{T}}_k$ be the class of graphs of treewidth at most $k$, and let ${\textup{\textsf{bt}}_{}(G)}$ denote the book thickness of a graph $G$. Ganley and Heath proved that…

Let $C_n$ denote an $n$-cycle, and let $C_m { \,\Box\,} C_n$ denote their Cartesian product. A graph $G$ is nearly dispersable when its matching book thickness satisfies…

Let $G$ be a regular bipartite graph, and let $mbt(G)$ and $\Delta(G)$ denote its maximum book thickness and maximum degree, respectively. Vertex-transitivity conjecture. The count…

Let $G$ be a vertex-transitive graph, let $\Delta(G)$ denote its maximum degree, and write $mbt(G)$ for its book thickness. Put $\Delta(G)=r$. Vertex-transitive book-thickness conj…

Let $G$ be a bipartite cubic planar graph. A subhamiltonian dispersable graph is one that has a subhamiltonian vertex ordering $[?]$ such that $mbt(G)=mbt(G,\omega)=3$. Dispersabil…

Let $G$ be a bipartite cubic planar graph, meaning that $G$ is bipartite, planar, and every vertex has degree three. A graph is dispersable if it has a proper $\Delta(G)$-edge-colo…

Let $K_n$ be the complete graph on $n$ vertices, let $\mathcal{E}_{c}(K_n)$ denote its complete expansion graph, and let $pn(G)$ be the pagenumber of a graph $G$. For a positive in…

Let $G$ be a $3$-regular bipartite planar graph. Its dispersable book thickness $dbt(G)$ is the minimum number of pages in a dispersable book embedding, and $G$ is dispersable when…

For a graph, book thickness is the minimum number of pages in a book embedding, and convex antithickness is the minimum number of convex geometric thrackles in a straight-line draw…

Blažek–Koman conjecture. For any positive integers $k$ and $n$,

Let $K_n$ be the complete graph on $n$ vertices, let $uk(Kn)$ denote its minimum number of crossings in a $k$-page book drawing, and let $Zk(n)$ denote the number of crossings in…

Heath and Pemmaraju's conjecture. Every $k$-tree has a $k$-page book embedding.