✦ LIBER ✦

Intersection Representation of Complete Unbalanced Bipartite Graphs

✍ Scribed by Nancy Eaton

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

No coin nor oath required. For personal study only.

✦ Synopsis

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 (K n, n )=n 2 . In 1992, Chung and West conjectured that for all graphs G on 2n vertices, % p (G) % p (K n, n ) when p 1. Subsequently, upper and lower bounds for % p (K n, n ) have been found to be (n 2 Âp)(1+o(1)). We show in this paper that many complete unbalanced bipartite graphs on 2n vertices have a larger p-intersection number than K n, n . For example, when p=2, %

1997 Academic Press the above argument, we can see that % p (G) % 1 (G)+ p&1 for all graphs G. Also, it is simple to prove that there exists a constant c such that c% 1 (G) 1Âp % p (G) for all graphs G ; see [2].

📜 SIMILAR VOLUMES

Bipartite Graphs Whose Edge Algebras Are

Bipartite Graphs Whose Edge Algebras Are Complete Intersections

✍ Mordechai Katzman 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 115 KB

Let R be a monomial subalgebra of k x 1 x N generated by square free monomials of degree two. This paper addresses the following question: when is R a complete intersection? For such a k-algebra we can associate a graph G whose vertices are x 1 x N and whose edges are x i x j x i x j ∈ R . Convers

Simultaneous intersection representation

Simultaneous intersection representation of pairs of graphs

✍ Tanenbaum, Paul J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB 👁 2 views

We characterize the pairs (G 1 , G 2 ) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G 1 is the intersection graph of the subsets and G 2 is the intersection graph of their complements. We also cons

On set intersection representations of g

On set intersection representations of graphs

✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract The intersection dimension of a bipartite graph with respect to a type __L__ is the smallest number __t__ for which it is possible to assign sets __A__~__x__~⊆{1, …, __t__} of labels to vertices __x__ so that any two vertices __x__ and __y__ from different parts are adjacent if and only

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

On the Pagenumber of Complete Bipartite

On the Pagenumber of Complete Bipartite Graphs

✍ Hikoe Enomoto; Tomoki Nakamigawa; Katsuhiro Ota 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 324 KB

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