Uncrossed number can differ arbitrarily from outerthickness
Let denote the uncrossed number of a graph , and let denote its outerthickness. For every positive integer , there is a graph such that
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
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.