Uncrossed number can differ arbitrarily from outerthickness

At least 1 year old · documented by

Let unc(G){\mathrm{unc}}(G) denote the uncrossed number of a graph GG, and let θo(G)\theta_o(G) denote its outerthickness. For every positive integer kk, there is a graph GG such that

θo(G)−unc(G)≥k.\theta_o(G)-{\mathrm{unc}}(G) \geq k.

Uncrossed-number separation conjecture. The uncrossed number can be arbitrarily far apart from the outerthickness. This conjecture asks whether the difference between these two graph parameters is unbounded; for the complete and complete bipartite graphs studied in the paper, their difference is never larger than one, so those classes do not establish the conjectured separation.

References

Primary source

Martin Balko, Petr Hliněný, Tomáš Masařík, Joachim Orthaber, Birgit Vogtenhuber and Mirko H. Wagner, “On the Uncrossed Number of Graphs”, arXiv:2407.21206 (2025).

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.