Uncrossed number can differ arbitrarily from outerthickness

From papers

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.

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

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).

Solutions 0

No solutions have been posted yet.