Autor:	Gruber, Hermann
Rok vydání:	2010
Předmět:	Computer Science - Discrete Mathematics Mathematics - Combinatorics 05C40 05C35
Zdroj:	Journal of Combinatorics, 3(4):669-681, 2012
Druh dokumentu:	Working Paper
Popis:	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(1 + log (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. Comment: Version 2: revised version, 8 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1012.1344 Zobrazit plný text záznamu View this record from Arxiv