کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654201 | 1632810 | 2010 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rank-width and tree-width of HH-minor-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We prove that for any fixed r≥2r≥2, the tree-width of graphs not containing KrKr 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 KrKr-minor free graphs and graphs of bounded genus.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 31, Issue 7, October 2010, Pages 1617–1628
Journal: European Journal of Combinatorics - Volume 31, Issue 7, October 2010, Pages 1617–1628
نویسندگان
Fedor V. Fomin, Sang-il Oum, Dimitrios M. Thilikos,