On the minimal degree condition of graphs implying some properties of subgraphs

2021/02/02 by Qian, Bingchen, Xie, Chengfei, Ge, Gennian
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2102.01338

Abstract

Erdős posed the problem of finding conditions on a graph G that imply the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We generalize this problem to general cases. Let δ_r be the least number so that any graph G on n vertices with minimum degree δ_rn has the property P_r-1(G)=K_rf(G), where P_r-1(G) is the largest number of edges in an (r-1)-partite subgraph and K_rf(G) is the largest number of edges in a K_r-free subgraph. We show that (3r-4)/(3r-1)

Related

• A proof of a conjecture of Erdős, Faudree, Rousseau and Schelp on subgraphs of minimum degree k
• Sparse vertex cutsets and the maximum degree
• Resolution of the Erdős-Sauer problem on regular subgraphs
• Smaller subgraphs of minimum degree k
• Stability and Erdős--Stone type results for F-free graphs with a fixed number of edges