Centre for Discrete and Applicable Mathematics |
|
CDAM Research Report, LSE-CDAM-2006-10September 2006 |
Forbidden Induced Bipartite Graphs
Peter Allen
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 faster than n^{cn} for any c. 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.A PDF file (243 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2006-10, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. |
||
Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk |
Introduction to the CDAM Research Report Series. | ||
CDAM Homepage. |