The obstacle-number graph-counting conjecture

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(nlog2n)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.

Sources & referencesView supporting material

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.