Dujmović–Morin conjecture on the number of graphs with bounded obstacle number
Dujmović–Morin conjecture on the number of graphs with bounded obstacle number
Given a graph , let its obstacle number be the minimum number of faces in a straight-line drawing whose union intersects every non-edge, and let denote the number of -vertex graphs with obstacle number at most . For positive integers and , the conjecture is
where . Dujmović–Morin conjecture. For all positive integers and , we have , where . This conjecture concerns the growth of the number of graphs admitting drawings with bounded obstacle number, and would constrain how many graphs can have small obstacle number. The cited context gives lower bounds on the maximum obstacle number, but does not state that this conjecture has been resolved.
Sources & referencesView supporting material
Primary source
Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr and Alexander Wolff, “Bounding and computing obstacle numbers of graphs”, arXiv:2206.15414 (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.