The crossing-number equality conjecture for complete tripartite graphs

Let n1,n2,n31n_1,n_2,n_3\geq 1, and let Kn1,n2,n3K_{n_1,n_2,n_3} be the complete tripartite graph with part sizes n1,n2,n3n_1,n_2,n_3. Write cr(G)\operatorname{cr}(G) for the crossing number of a graph GG, and cr(G)\overline{\operatorname{cr}}(G) for its rectilinear crossing number, the minimum number of crossings in a straight-line drawing of GG.

Crossing-number equality conjecture.

cr(Kn1,n2,n3)=cr(Kn1,n2,n3).\overline{\operatorname{cr}}(K_{n_1,n_2,n_3})=\operatorname{cr}(K_{n_1,n_2,n_3}).

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

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.