Lozin, Vadim V. and Zamaraev, Victor (2017) The structure and the number of $P_7$-free bipartite graphs. European Journal of Combinatorics, 65 . pp. 143-153. doi:10.1016/j.ejc.2017.05.008 ISSN 0195-6698.

Preview

PDF WRAP-structure-number-bipartite-graphs-Lozin-2017.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (732Kb) | Preview

Request Changes to record.

Abstract

We show that the number of labelled P7-free bipartite graphs with n vertices grows as nΘ(n). This resolves an open problem posed by Allen (2009), and completes the description of speeds of monogenic classes of bipartite graphs. Our solution is based on a new decomposition scheme of bipartite graphs, which is of independent interest.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH):	Bipartite graphs, Combinatorial analysis
Journal or Publication Title:	European Journal of Combinatorics
Publisher:	Academic Press
ISSN:	0195-6698
Official Date:	October 2017
Dates:	Date Event October 2017 Published 19 June 2017 Available 24 May 2017 Accepted
Volume:	65
Page Range:	pp. 143-153
DOI:	10.1016/j.ejc.2017.05.008
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	27 June 2017
Date of first compliant Open Access:	27 June 2017
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	EP/L020408/1 (EPSRC)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads