The plane-path conjecture for complete simple topological graphs
The plane-path conjecture for complete simple topological graphs
A simple topological graph is a graph drawn in the plane so that vertices are distinct points, edges are simple arcs joining their endpoints, no edge contains a vertex other than its endpoints, and every pair of edges intersects at most once, either at a common endpoint or at a proper crossing. A plane path is a path whose edges are pairwise noncrossing. The length of a path is its number of edges.
Plane-path conjecture. There is an absolute constant such that every complete -vertex simple topological graph contains a plane path of length .
This conjecture asks for a polynomial-length plane path in every complete simple topological graph. The context notes that related results guarantee many pairwise disjoint edges, but the corresponding polynomial bound for plane paths remains open.
Sources & referencesView supporting material
Primary source
Andrew Suk and Ji Zeng, “Unavoidable patterns in complete simple topological graphs”, arXiv:2204.04293 (2022).
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
Sign in to submit a solution.
No solutions have been posted yet.