Premium
Pagenumber of complete bipartite graphs
Author(s) -
Muder Douglas J.,
Weaver Margaret Lefevre,
West Douglas B.
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120403
Subject(s) - combinatorics , mathematics , conjecture , bipartite graph , partition (number theory) , embedding , vertex (graph theory) , discrete mathematics , graph , computer science , artificial intelligence
Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t(G) (also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showing t(K m,n ) ⩽ ⌈( m + 2 n )/4⌉, which we conjecture optimal. We prove a result suggesting this is optimal for m ⩾ 2 n − 3. For the most difficult case m = n , we consider vertex permutations that are regular , i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ⌈(7 n − 2)/9⌉ pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.