کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652673 1632601 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Even-hole-free planar graphs have bounded treewidth
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Even-hole-free planar graphs have bounded treewidth
چکیده انگلیسی

The class of planar graphs has unbounded treewidth, since the k×k grid, ∀k∈N, is planar and has treewidth k. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if G is an even-hole-free planar graph, then it does not contain a 9 × 9 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 44.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 30, 20 February 2008, Pages 129-134