The structure and the number of <i>P</i><sub>7</sub>-free bipartite graphs


Lozin, Vadim and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2017) The structure and the number of <i>P</i><sub>7</sub>-free bipartite graphs. EUROPEAN JOURNAL OF COMBINATORICS, 65. pp. 143-153.

[img] Text
1607.08782v1.pdf - Submitted version
Download (196kB) | Preview

Abstract

We show that the number of labelled $P_7$-free bipartite graphs with $n$ vertices grows as $n^{\Theta(n)}$. This resolves an open problem posed by Allen [P. Allen, Forbidden induced bipartite graphs. J. Graph Theory 60 (2009), no. 3, 219--241.], 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: Article
Uncontrolled Keywords: math.CO, math.CO
Depositing User: Symplectic Admin
Date Deposited: 07 Sep 2020 07:57
Last Modified: 14 Oct 2023 13:33
DOI: 10.1016/j.ejc.2017.05.008
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3100229
Dimensions
Altmetric
CORE (COnnecting REpositories)