On obstacle numbers (Q2517647): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1308.4321 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3503433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Obstacle numbers of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3267900 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convex Obstacle Numbers of Outerplanar Graphs and Bipartite Permutation Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower bounds on the obstacle number of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs with Large Obstacle Numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of graphs with low obstacle number / rank | |||
Normal rank |
Latest revision as of 16:20, 10 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On obstacle numbers |
scientific article |
Statements
On obstacle numbers (English)
0 references
27 August 2015
0 references
Summary: The obstacle number is a new graph parameter introduced by \textit{H. Alpert} et al. [Discrete Comput. Geom. 44, No. 1, 223--244 (2010; Zbl 1216.05088)]. \textit{P. Mukkamala} et al. [Electron. J. Comb. 19, No. 2, Research Paper P32, 8 p. (2012; Zbl 1243.05176)] 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. [loc. cit.] 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.
0 references