A problem on sparse induced subgraphs
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
Problem (proposed by Erdös [1])
Let \(f(n,k)\) denote the smallest integer for which there is a graph with \(n\) vertices and \(f(n,k)\) edges so that every set of \(k+2\) vertices induces a subgraph with maximum degree at least \(k\). Determine \(f(n,k)\).
Bibliography  

1  R. Faudree, C. C. Rousseau and R. H. Schelp,
Problems in graph theory from Memphis,
The Mathematics of Paul Erdös, II (R. L. Graham and J.
Nešetril, eds.), 726, SpringerVerlag, Berlin, 1996.
