Rank-width and tree-width of H-minor-free graphs
We prove that for any fixed r >= 2, the tree-width of graphs not containing K(r) as a topological minor (resp. as a subgraph) is bounded by a linear (resp. polynomial) function of their rank-width. We also present refinements of our bounds for other graph classes such as K(r)-minor free graphs and graphs of bounded genus. (C) 2010 Elsevier Ltd. All rights reserved.
- Publisher
- ACADEMIC PRESS LTD
- Issue Date
- 2010-10
- Language
- English
- Article Type
- Article
- Keywords
CLIQUE-WIDTH; BOUNDED EXPANSION; EXTREMAL FUNCTION; BRANCH-WIDTH; NUMBER; GRAD
- Citation
EUROPEAN JOURNAL OF COMBINATORICS, v.31, no.7, pp.1617 - 1628
- ISSN
- 0195-6698
- Appears in Collection
- MA-Journal Papers(저널논문)
- Files in This Item
- There are no files associated with this item.
This item is cited by other documents in WoS
| ⊙ Detail Information in WoSⓡ | Click to see |  |
| ⊙ Cited 18 items in WoS | Click to see citing articles in |  |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.