The crossing-number equality conjecture 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. 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.

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.