3
$\begingroup$

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 book thickness $bt(G)$ is the minimum number of pages in which the graph $G$ can be embedded.

I wondered whether the following result is right:

Let $ {K_n}$ be a complete graph with $n$ order, a graph $ {K'_n}$ is from the graph $K_n$ by adding at most one new vertex on each edge $e$ of $K_n$, then $bt( {K'_n})=bt(K_n).$

I would be very grateful if someone could give any suggestions.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I will point out that there already exists a tag called (extremal-graph-theory). So if this is what you had in mind, there is no need to create a new tag. (And if there is some distinction between extreme graph theory and extremal graph theory, it would be good to clarify that in the tag-info.) $\endgroup$
    – Martin Sleziak
    Commented Dec 1, 2019 at 19:18
  • $\begingroup$ Can you do $K_5$ with each edge subdivided, on 3 pages? I doubt it. $\endgroup$
    – Brendan McKay
    Commented Jun 4, 2020 at 11:57
  • $\begingroup$ I take it back; $K_5$ subdivided can be done. $\endgroup$
    – Brendan McKay
    Commented Jun 4, 2020 at 12:03

0

Reset to default

You must log in to answer this question.