کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903853 1632962 2018 34 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The extremal function for Petersen minors
ترجمه فارسی عنوان
عملکرد افراطی برای کودکان زیرزمینی پترسن
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We prove that every graph with n vertices and at least 5n−8 edges contains the Petersen graph as a minor, and this bound is best possible. Moreover we characterise all Petersen-minor-free graphs with at least 5n−11 edges. It follows that every graph containing no Petersen minor is 9-colourable and has vertex arboricity at most 5. These results are also best possible.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 131, July 2018, Pages 220-253
نویسندگان
, ,