Back to Search
Start Over
Exact bipartite Tur\'an numbers of large even cycles
- Source :
- J. Graph Theory 97 (2021), no. 4, 642--656
- Publication Year :
- 2019
-
Abstract
- Let the bipartite Tur\'an number $ex(m,n,H)$ of a graph $H$ be the maximum number of edges in an $H$-free bipartite graph with two parts of sizes $m$ and $n$, respectively. In this paper, we prove that $ex(m,n,C_{2t})=(t-1)n+m-t+1$ for any positive integers $m,n,t$ with $n\geq m\geq t\geq \frac{m}{2}+1$. This confirms the rest of a conjecture of Gy\"{o}ri \cite{G97} (in a stronger form), and improves the upper bound of $ex(m,n,C_{2t})$ obtained by Jiang and Ma \cite{JM18} for this range. We also prove a tight edge condition for consecutive even cycles in bipartite graphs, which settles a conjecture in \cite{A09}. As a main tool, for a longest cycle $C$ in a bipartite graph, we obtain an estimate on the upper bound of the number of edges which are incident to at most one vertex in $C$. Our two results generalize or sharpen a classical theorem due to Jackson \cite{J85} in different ways.<br />Comment: Revised version; 16 pages
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- J. Graph Theory 97 (2021), no. 4, 642--656
- Publication Type :
- Report
- Accession number :
- edsarx.1901.06137
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1002/jgt.22676