http://openproblemgarden.org/op/book_thickness_of_subdivisions Comments for "Book Thickness of Subdivisions" en http://openproblemgarden.org/op/book_thickness_of_subdivisions#comment-93666 <p>This problem is solved in:</p> <p>V. Dujmović, D. Eppstein, R. Hickingbotham, P. Morin, D. R. Wood. Stack-number is not bounded by queue-number. Combinatorica, accepted in 2021 https://arxiv.org/abs/2011.04195</p> Sat, 10 Jul 2021 14:52:34 +0200 Anonymous comment 93666 at http://openproblemgarden.org http://openproblemgarden.org/op/book_thickness_of_subdivisions <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/blankenship_robin">Blankenship</a>; <a href="/category/oporowski_bogdan">Oporowski</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a finite undirected simple graph.</p> <p>A <em><img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-page book embedding</em> of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> consists of a linear order <img class="teximage" src="/files/tex/c7a95bb4e8a6abbf58d88b1e20b8008ab99a95a9.png" alt="$ \preceq $" /> of <img class="teximage" src="/files/tex/b324b54d8674fa66eb7e616b03c7a601ccdab6b8.png" alt="$ V(G) $" /> and a (non-proper) <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-colouring of <img class="teximage" src="/files/tex/4b556e49b77160d4c8a0131e0efdfefd52dda2bb.png" alt="$ E(G) $" /> such that edges with the same colour do not cross with respect to <img class="teximage" src="/files/tex/c7a95bb4e8a6abbf58d88b1e20b8008ab99a95a9.png" alt="$ \preceq $" />. That is, if <img class="teximage" src="/files/tex/ba49bdd7c7aa488da27ec50d884225c30f5b358d.png" alt="$ v\prec x\prec w\prec y $" /> for some edges <img class="teximage" src="/files/tex/78d3c22391e05e748a91476681ec63469636de46.png" alt="$ vw,xy\in E(G) $" />, then <img class="teximage" src="/files/tex/055e0215ab4d6ae92d2568bcc1b16d9bdc66498f.png" alt="$ vw $" /> and <img class="teximage" src="/files/tex/39834c9449acbf29f08da826e15123c18a148479.png" alt="$ xy $" /> receive distinct colours. </p> <p>One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.</p> <p>The <em>book thickness</em> of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, denoted by bt<img class="teximage" src="/files/tex/b1a426656fa2f0ba9bb026e5941d8cc8838b049d.png" alt="$ (G) $" /> is the minimum integer <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> for which there is a <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-page book embedding of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />.</p> <p>Let <img class="teximage" src="/files/tex/4f0441f0f10868fdec44e318cf632c2a083e07be.png" alt="$ G&#039; $" /> be the graph obtained by subdividing each edge of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> exactly once.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; There is a function <img class="teximage" src="/files/tex/43374150a8a220f67049937b9790b7d28eb17fb9.png" alt="$ f $" /> such that for every graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />, <img class="teximage" src="/files/tex/0aedb9a9a46520e4c6b7a352924b0c2e2fc329d6.png" alt="$$ \text{bt}(G) \leq f( \text{bt}(G&#039;) )\enspace. $$" /> </div> </tr></td> </table> </td> </tr> </table> Blankenship, Robin Oporowski, Bogdan book embedding book thickness Graph Theory http://openproblemgarden.org/op/book_thickness_of_subdivisions#comment Mon, 19 Jan 2009 02:32:50 +0100 David Wood 34908 at http://openproblemgarden.org