Strict crossing-number separation for balanced complete 4-partite graphs

From papers

Let Kn4K_n^4 denote the complete balanced 44-partite graph with nn vertices, and let cr(G)\operatorname{cr}(G) and cr(G)\overline{\operatorname{cr}}(G) denote respectively its ordinary and rectilinear crossing numbers. 4-partite separation conjecture. There exists a natural number n0>9n_0>9 such that, for every nn0n\geq n_0,

cr(Kn4)<cr(Kn4).\operatorname{cr}(K_n^4)<\overline{\operatorname{cr}}(K_n^4).

The known values and upper bounds at n=8,9n=8,9 motivate the conjecture that, eventually, straight-line drawings require strictly more crossings than unrestricted drawings. The source does not determine such an n0n_0.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ruy Fabila-Monroy, Rosna Paul, Jenifer Viafara-Chanchi and Alexandra Weinberger, “On the rectilinear crossing number of complete balanced multipartite graphs and layered graphs”, arXiv:2404.13155 (2025).

Solutions 0

No solutions have been posted yet.