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

DOI10.1007/S00373-017-1767-6MaRDI QIDQ2014230zbMATH OpenOpenAlexWikidataFDO

Authors Long-Tu Yuan, Xiao-Dong Zhang

Publication date 10 August 2017

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

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

zbMATH Keywords

treebipartite graphextremal graphErdős-Sós conjecture

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)