The product-structure conjecture above the independent-crossing threshold

Let nn be a positive integer, let s(n)s(n) be the threshold defined in the paper, and let α\alpha be a parameter. Consider the class of intersection graphs of α\alpha-free homothetic regular nn-gons.

The above-threshold product-structure conjecture. For every αs(n)\alpha \geq s(n), the class of intersection graphs of α\alpha-free homothetic regular nn-gons has product structure.

For αs(n)\alpha\geq s(n), the paper proves that the canonical drawings are kk-independent crossing with k=26(n+1)k=26(n+1). The assertion would follow from the conjectured product structure for all kk-independent crossing graph classes.

Sources & referencesView supporting material

Primary source

Laura Merker, Lena Scherzer, Samuel Schneider and Torsten Ueckerdt, “Intersection Graphs with and without Product Structure”, arXiv:2409.01732 (2024).

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.