Unbounded gap conjecture between outerthickness and uncrossed number

At least 6 years old · documented by

Let θo(G)\theta_o(G) denote the outerthickness of a graph GG, and let unc⁡(G)\operatorname{unc}(G) denote its uncrossed number. Unbounded-gap conjecture. For every positive integer kk, there exists a graph GG such that

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

This conjecture is attributed in the source to a prior conjecture and would follow from proving tightness of the paper's bound for a suitable constant-density graph class. Its resolution would establish that the difference between outerthickness and uncrossed number is unbounded.

References

Primary source

Gaspard Charvy and Tomáš Masařík, “General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number”, arXiv:2507.20937 (2026).

Additional references

6 papers in this index state this conjecture (2019–2025). The statement above is taken from the most recent of them; the others are arXiv:2412.09797, arXiv:2312.04925, arXiv:2008.04282, arXiv:2008.09265, arXiv:1901.07967.

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.