The obstacle-number graph-counting conjecture

About 13 years old · traced to

Let f(h,n)f(h,n) denote the number of nn-vertex graphs with obstacle number at most hh. The function g(n)g(n) satisfies g(n)∈O(nlog⁡2n)g(n)\in O(n\log^2 n).

Obstacle-number graph-counting conjecture. The number of such graphs satisfies

f(h,n)≤2g(n)⋅o(h).f(h,n)\leq 2^{g(n)\cdot o(h)}.

An improved upper bound on the dependence of the counting function on hh would improve lower bounds for the worst-case obstacle number of graphs. The paper presents this as a conjectural direction; no resolution is given.

References

Primary source

Vida Dujmović and Pat Morin, “On Obstacle Numbers”, arXiv:1308.4321 (2013).

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.