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.), 7-26, Springer-Verlag, Berlin, 1996.
|