The potential crossing pair characterization of graphs with crossing number at least 2
The potential crossing pair characterization of graphs with crossing number at least 2
Let be a non-planar graph. A pair of edges of is a potential crossing pair if, for every Kuratowski subgraph of , and form a crossing pair of . The crossing number of , denoted by , is the minimum number of crossings in a drawing of in the plane.
Potential crossing pair conjecture. The graph has crossing number at least if and only if it does not have a potential crossing pair.
This question arises from the characterization of crossing pairs in the preceding theorem: a potential crossing pair that is not separated by cycles is a crossing pair. Thus, any potential crossing pair in a graph with crossing number at least would necessarily be separated by cycles. The source does not provide a resolution of this characterization.
Sources & referencesView supporting material
Primary source
André C. Silva, Alan Arroyo, R. Bruce Richter and Orlando Lee, “Graphs with at most one crossing”, arXiv:1901.09955 (2019).
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.