The crossing-number equality conjecture for complete tripartite graphs
The crossing-number equality conjecture for complete tripartite graphs
Let , and let be the complete tripartite graph with part sizes . Write for the crossing number of a graph , and for its rectilinear crossing number, the minimum number of crossings in a straight-line drawing of .
Crossing-number equality conjecture.
Since every rectilinear drawing is a planar drawing, the left-hand side is always at least the ordinary crossing number. The conjecture asserts that complete tripartite graphs always admit optimal straight-line drawings; the supplied context gives evidence from the preceding bounds but no resolution.
Sources & referencesView supporting material
Primary source
Ellen Gethner, Leslie Hogben, Bernard Lidický, Florian Pfender, Amanda Ruiz and Michael Young, “Crossing numbers of complete tripartite and balanced complete multipartite graphs”, arXiv:1410.0720 (2014).
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.