The rectilinear crossing-number formula for complete tripartite graphs

About 12 years old · traced to

Let n1,n2,n3≥1n_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.

References

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.