✦ LIBER ✦

Forbidden induced bipartite graphs

✍ Scribed by Peter Allen

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 210 KB
Volume: 60
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20355

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a fixed bipartite graph H, we study the asymptotic speed of growth of the number of bipartite graphs on n vertices which do not contain an induced copy of H. Whenever H contains either a cycle or the bipartite complement of a cycle, the speed of growth is ${{2}}^{\Omega({{n}}^{{{{6}}\over {{5}}}})}$. For every other bipartite graph except the path on seven vertices, we are able to find both upper and lower bounds of the form ${{n}}^{{{cn}}+{{o}}({{n}})}$. In many cases we are able to determine the correct value of c. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 219–241, 2009

📜 SIMILAR VOLUMES

Koszul Bipartite Graphs

✍ Hidefumi Ohsugi; Takayuki Hibi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 48 KB

Cellular Bipartite Graphs

✍ Hans-Jürgen Bandelt; Victor Chepoi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 310 KB

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Line Graphs and Forbidden Induced Subgra

Line Graphs and Forbidden Induced Subgraphs

✍ Hong-Jian Lai; Ľubomı&#x0301;r Šoltés 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Beineke and Robertson independently characterized line graphs in terms of nine forbidden induced subgraphs. In 1994, S8 olte s gave another characterization, which reduces the number of forbidden induced subgraphs to seven, with only five exceptional cases. A graph is said to be a dumbbell if it con

Characterizing path graphs by forbidden

Characterizing path graphs by forbidden induced subgraphs

✍ Benjamin Lévêque; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009

Embeddings of bipartite graphs

✍ Mohammed Abu-Sbeih; T. D. Parsons 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB