1987 Reports

On 3-Pushdown Graphs With Large Separators

Galil, Zvi; Kannan, Ravi; Szemeredi, Endre

For an integer s let ZS(n), the s-iterated logarithm function, be defined inductively: [O(n) = n, [8+1(n) = log2(l8(n)) for s 2:: o. We show that for every fixed s and all n large enough, there is an n-vertex 3-pushdown graph whose smallest separator contains at least n(n/[8(n)) vertices.