The rectilinear crossing-number formula 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. Its rectilinear crossing number, denoted by cr(Kn1,n2,n3)\overline{\operatorname{cr}}(K_{n_1,n_2,n_3}), is the minimum number of crossings in a drawing in which every edge is a straight line segment. Let A(n1,n2,n3)A(n_1,n_2,n_3) be the upper-bound expression defined in the paper.

Rectilinear crossing-number conjecture.

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

The preceding upper and lower bounds provide evidence for this formula, which is known in several cases where two parts are small but remains open in general.

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.