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

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
نویسندگان
, , ,