A variation of the Erdős-Sós conjecture in bipartite graphs

DOI10.1007/S00373-017-1767-6zbMATH Open1368.05077arXiv1702.03060OpenAlexW2586280130WikidataQ123029552 ScholiaQ123029552MaRDI QIDQ2014230FDOQ2014230

Authors: Long-Tu Yuan, Xiao-Dong Zhang 

Publication date: 10 August 2017

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: The ErdH{o}s-S'{o}s Conjecture states that every graph with average degree more than $k-2$ contains all trees of order $k$ as subgraphs. In this paper, we consider a variation of the above conjecture: studying the maximum size of an $(n,m)$-bipartite graph which does not contain all $(k,l)$-bipartite trees for given integers $ngem$ and $kgel$. In particular, we determine that the maximum size of an $(n,m)$-bipartite graph which does not contain all $(n,m)$-bipartite trees as subgraphs (or all $(k,2)$-bipartite trees as subgraphs, respectively). Furthermore, all these extremal graphs are characterized.

Full work available at URL: https://arxiv.org/abs/1702.03060

Recommendations

• Bipartite version of the Erdös-Sós conjecture
• A variant of the Erdős-Sós conjecture
• A variation of a conjecture due to Erdös and Sós
• On the Erdős-Sós conjecture for graphs on \(n = k + 4\) vertices
• A Local Approach to the Erdös--Sós Conjecture

zbMATH Keywords

treebipartite graphextremal graphErdős-Sós conjecture

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Cites Work

• On Hamilton's ideals
• The Erdös-Sós conjecture for graphs without \(C_ 4\)
• The Erdös-Sós conjecture for graphs of girth 5
• Constructing Trees in Graphs whose Complement has no K_2,s
• On maximal paths and circuits of graphs
• On the Erd�s-S�s conjecture
• The history of degenerate (bipartite) extremal graph problems
• An extremal problem for paths in bipartite graphs
• On the Erdős-Sós conjecture for graphs on \(n=k+3\) vertices.
• Title not available (Why is that?)
• The Erdős‐Sós Conjecture for trees of diameter four
• Constructing trees in graphs with no K_2,s
• On a problem of K. Zarankiewicz
• Asymptotic solution for a new class of forbidden r-graphs
• On the Turán number for the hexagon
• \(C_ 6\)-free bipartite graphs and product representation of squares
• On the Erdős-Sós conjecture and graphs with large minimum degree.
• On Hamiltonian bipartite graphs
• The Erdős-Sós conjecture for spiders of large size
• Cycles in bipartite graphs and an application in number theory
• Counterexample to a conjecture of Györi on \(C_{2l}\)-free bipartite graphs
• On the Erdős-Sós conjecture for graphs on \(n = k + 4\) vertices

Cited In (2)

• Bipartite version of the Erdös-Sós conjecture
• Kalai's conjecture in \(r\)-partite \(r\)-graphs

This page was built for publication: A variation of the Erdős-Sós conjecture in bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2014230)