Erdős Problem #1018 — Small nonplanar subgraphs in moderately dense graphs
For a finite simple graph , write for its number of edges, and let a subgraph mean an ordinary, not necessarily induced, subgraph. The question is whether, for every real , there are a constant and an integer such that for every integer and every -vertex graph ,
implies that contains a nonplanar subgraph with . For simple graphs the substantive range is ; for the edge condition is impossible for all sufficiently large . Erdős Problem #1018 Jiang (2011)
Background
Erdős posed the question in 1971. A graph with more than edges cannot itself be planar, but that only gives a nonplanar subgraph whose order may grow with . The problem asks whether a modest superlinear edge count forces a witness of bounded order. Erdős also observed that any such bound must grow without bound as tends to zero. The role of the exponent is natural in light of high-girth constructions: for , graphs can have on the order of edges while having girth at least , which forces subdivisions of complete graphs to use many vertices as decreases. Erdős Problem #1018 Jiang (2011)
References
P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97–109.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.