The obstacle number is a new graph parameter introduced by Alpert, Koch, and Laison (2010). Mukkamala et al. (2012) show that there exist graphs with $n$ vertices having obstacle number in $\Omega(n/\log n)$. In this note, we up this lower bound to $\Omega(n/(\log\log n)^2)$. Our proof makes use of an upper bound of Mukkamala et al. on the number of graphs having obstacle number at most $h$ in such a way that any subsequent improvements to their upper bound will improve our lower bound.
@article{10_37236_4373,
author = {Vida Dujmovi\'c and Pat Morin},
title = {On obstacle numbers},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {3},
doi = {10.37236/4373},
zbl = {1325.05093},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4373/}
}
TY - JOUR
AU - Vida Dujmović
AU - Pat Morin
TI - On obstacle numbers
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4373/
DO - 10.37236/4373
ID - 10_37236_4373
ER -
%0 Journal Article
%A Vida Dujmović
%A Pat Morin
%T On obstacle numbers
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4373/
%R 10.37236/4373
%F 10_37236_4373
Vida Dujmović; Pat Morin. On obstacle numbers. The electronic journal of combinatorics, Tome 22 (2015) no. 3. doi: 10.37236/4373
