Journal of Combinatorics

Volume 3 (2012)

Number 4

On balanced separators, treewidth, and cycle rank

Pages: 669 – 681

DOI: http://dx.doi.org/10.4310/JOC.2012.v3.n4.a5

Author

Hermann Gruber (Knowledgepark AG, München, Germany)

Abstract

We investigate relations between different width parameters of graphs, in particular balanced separator number, treewidth, and cycle rank. Our main result states that a graph with balanced separator number $k$ has treewidth at least $k$ but cycle rank at most $k \cdot(1 + \log \frac{n}{k})$, thus refining the previously known bounds, as stated by Robertson and Seymour (1986) and by Bodlaender et al. (1995). Furthermore, we show that the improved bounds are best possible.

Keywords

vertex separator, treewidth, pathwidth, bandwidth, cycle rank, ordered coloring, vertex ranking, hypercube

2010 Mathematics Subject Classification

05C35, 05C40

Full Text (PDF format)