The product-structure conjecture above the independent-crossing threshold
The product-structure conjecture above the independent-crossing threshold
Let be a positive integer, let be the threshold defined in the paper, and let be a parameter. Consider the class of intersection graphs of -free homothetic regular -gons.
The above-threshold product-structure conjecture. For every , the class of intersection graphs of -free homothetic regular -gons has product structure.
For , the paper proves that the canonical drawings are -independent crossing with . The assertion would follow from the conjectured product structure for all -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.