Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647654 | Discrete Mathematics | 2013 | 8 Pages |
Abstract
A book embedding of a graph G is a pair consisting of an edge-coloring of G and a circular ordering of the vertices of G, such that if we place the vertices in the given ordering on a circle and draw the edges as straight lines in the inner part of the circle, then no two edges of the same color cross. The page numberp(G) is the smallest number of colors within which G can be book embedded. We generalize the matrix representation of Muder, Weaver, and West for book embeddings of complete bipartite graphs to a representation for all graphs. Furthermore, we prove a new upper bound for the page number of complete odd-partite graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Konrad Sperfeld,