# Book thickness of covering graph II

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded.

Let $$G$$ is a finite covering graph of a graph $$B$$. The covering graph is more complicated than the basis graph. Hence at the beginning , I thought that $$pn(G)$$ should be no less than $$pn(B)$$ in general. Until Jan Kyncl give a counter-example: The graph of the icosahedron is a 2-fold cover of K6, but $$pn(icosahedron)=2$$ , $$pn(K_6)=3$$. Does $$pn(G)\geq pn(B)-1$$ hold in general?

• If $G$ could be infinite, then for an arbitrary $B$ we can take $G$ as the universal cover, which is a tree and has page number 1. For finite $G$ some lower bound on its page number may be obtained from the average degree of $B$. – Jan Kyncl Jun 28 '19 at 0:33
• @Jan Kyncl . Yes. if $G$ is infinite covering, then it is a tree. so pagenumber is 1. But how to get the lower bound by the average degree of base graph $B$？ Could you explain for it? – Jacob.Z.Lee Jun 28 '19 at 4:57
• If $B$ is connected and $G$ finite cover of $B$, then the average degree of $G$ is equal to the average degree of $B$. Now the subgraph of $G$ contained in each page of a book embedding is outerplanar, even when adding the Hamiltonian path or cycle joining consecutive vertices of the spine. This gives an upper bound on the average degree of $G$ approximately $2(pn(G)+1)$. – Jan Kyncl Jun 29 '19 at 1:46
• @JanKyncl Thanks. Actually, if $G$ is a graph with $V$ vetices, $E$ edges, then $pn(G)\geq [\frac{E-V}{V-3}]>\frac{E-V}{V}$. – Jacob.Z.Lee Jun 30 '19 at 9:14