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.
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 |