✦ LIBER ✦

On the Pagenumber of Complete Bipartite Graphs

✍ Scribed by Hikoe Enomoto; Tomoki Nakamigawa; Katsuhiro Ota

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 324 KB
Volume: 71
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1773

No coin nor oath required. For personal study only.

✦ Synopsis

The pagenumber p(G) of a graph G is defined as the smallest n such that G can be embedded in a book with n pages. We give an upper bound for the pagenumber of the complete bipartite graph K m, n . Among other things, we prove p(K n, n ) w2nÂ3x+1 and p(K wn 2 Â4x, n ) n&1. We also give an asymptotic result: min[m : p(K m, n )=n]=n 2 Â4+O(n 7Â4 ).

📜 SIMILAR VOLUMES

On the decomposition of kn into complete

On the decomposition of kn into complete bipartite graphs

✍ H. Tverberg 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 1 views

## Abstract A short proof is given of the impossibility of decomposing the complete graph on __n__ vertices into __n__‐2 or fewer complete bipartite graphs.

Hall parameters of complete and complete

Hall parameters of complete and complete bipartite graphs

✍ M. M. Cropper; A. J. W. Hilton 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 287 KB

## Abstract Given a graph __G__, for each υ ∈__V__(__G__) let __L__(υ) be a list assignment to __G__. The well‐known choice number __c__(__G__) is the least integer __j__ such that if |__L__(υ)| ≥__j__ for all υ ∈__V__(__G__), then __G__ has a proper vertex colouring ϕ with ϕ(υ) ∈ __L__ (υ) (∀υ ∈__

Regular orientable embeddings of complet

Regular orientable embeddings of complete bipartite graphs

✍ Jin Ho Kwak; Young Soo Kwon 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph __K__~__n,n__~ are in one‐to‐one correspondence with the permutations on __n__ elements satisfying a given criterion, and the isomorphism classes of them are com

Intersection Representation of Complete

Intersection Representation of Complete Unbalanced Bipartite Graphs

✍ Nancy Eaton 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 282 KB

A p-intersection representation of a graph G is a map, f, that assigns each vertex a subset of [1, 2, ..., t] The symbol % p (G) denotes this minimum t such that a p-intersection representation of G exists. In 1966 Erdo s, Goodman, and Po sa showed that for all graphs G on 2n vertices, % 1 (G) % 1

NP completeness of the edge precoloring

NP completeness of the edge precoloring extension problem on bipartite graphs

✍ Jiří Fiala 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

The chromaticity of complete bipartite g

The chromaticity of complete bipartite graphs with at most one edge deleted

✍ C. P. Teo; K. M. Koh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 364 KB 👁 1 views

## Abstract Let __K(p, q), p ≤ q__, denote the complete bipartite graph in which the two partite sets consist of __p__ and __q__ vertices, respectively. In this paper, we prove that (1) the graph __K(p, q)__ is chromatically unique if __p__ ≥ 2; and (2) the graph __K(p, q)__ ‐ __e__ obtained by del