Erdős Problem #1018 — Small nonplanar subgraphs in moderately dense graphs
For every , is there a constant such that every -vertex graph with edges contains a nonplanar subgraph on at most vertices?
References
Additional 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
Never refreshed
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.