2017/02/10 by Yuan, Long-Tu, Zhang, Xiao-Dong
#05C05 #05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1702.03060
The Erdős-Só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 n≥ m and k≥ l. 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.