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

preprint2021arXivOpen access

Abstract

Erdős posed the problem of finding conditions on a graph GG 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δ_r be the least number so that any graph GG on nn vertices with minimum degree δrnδ_rn has the property Pr−1(G)=Krf(G),P_{r-1}(G)=K_rf(G), where Pr−1(G)P_{r-1}(G) is the largest number of edges in an (r−1)(r-1)-partite subgraph and Krf(G)K_rf(G) is the largest number of edges in a KrK_r-free subgraph. We show that 3r−43r−1<δr≤4(3r−7)(r−1)+14(r−2)(3r−4)\frac{3r-4}{3r-1}<δ_r\le\frac{4(3r-7)(r-1)+1}{4(r-2)(3r-4)} when r≥4.r\ge4. In particular, δ4≤0.9415.δ_4\le 0.9415.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.