Exact bipartite Turán numbers of large even cycles
Binlong Li, Bo Ning
Abstract
Binlong Li, Bo Ning
Abstract
Abstract The bipartite Turán number, denoted by , is the maximum number of edges in an ‐free bipartite graph with two parts of sizes and , respectively. In this article, we prove for any positive integers with , which confirms (in a strong form) the unsolved case of a conjecture of Győri. Let be a bipartite graph with and . Suppose that for some . We prove that contains cycles of all even lengths from 4 to if . This result sharpens a theorem on long cycles in bipartite graphs due to Jackson. As a main tool, for a longest cycle in a bipartite graph, we prove an upper bound of the number of edges which are incident with at most one vertex in , which is a bipartite analogue of a classical theorem of Bondy. Our proof technique is structural.
OpenAlex reports 9 citations for this work. Citation counts describe recorded attention and do not establish research quality.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
Abstract The bipartite Turán number, denoted by , is the maximum number of edges in an ‐free bipartite graph with two parts of sizes and , respectively. In this article, we prove for any positive integers with , which confirms (in a strong form) the unsolved case of a conjecture of Győri. Let be a bipartite graph with and . Suppose that for some . We prove that contains cycles of all even lengths from 4 to if . This result sharpens a theorem on long cycles in bipartite graphs due to Jackson. As a main tool, for a longest cycle in a bipartite graph, we prove an upper bound of the number of edges which are incident with at most one vertex in , which is a bipartite analogue of a classical theorem of Bondy. Our proof technique is structural.
Key concepts: Bipartite graph, Combinatorics, Mathematics, Complete bipartite graph, Conjecture, Edge-transitive graph, Vertex (graph theory), Graph