کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10151237 685009 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Infinitely many minimal classes of graphs of unbounded clique-width
ترجمه فارسی عنوان
بی نهایت تعداد بسیار کم کلاس های گرافیکی از کلیدهای عرض نا محدود
کلمات کلیدی
کلیدهای عرض، فاصله کلاسی خطی، کلاس ارثی،
ترجمه چکیده
قضیه مشهور رابرتسون و سیمور بیان می کند که در خانواده کلاس های گراف کوچک و کوچک، کلاس های منحصر بفرد منحصر به فردی از عرض درختی بی حد و حصر وجود دارد، یعنی کلاس گراف های مسطح. در مورد عرض درخت، محدودیت به کلاس های جزئی بسته با این واقعیت که عرض درخت یک گراف هرگز کوچکتر از عرض درخت هر یک از افراد زیر آن است توجیه است. با این حال، این مورد در رابطه با عرض کلاسی نیست، زیرا عرض کلاسی یک گراف می تواند (بسیار) کوچکتر از عرض کلاسی آن جزئی باشد. از سوی دیگر، عرض کلاسی یک گراف هرگز کوچکتر از عرض کلاسی هر یک از زیرگراف های القا شده آن نیست، که به ما اجازه می دهد که محدود به کلاس های موروثی (یعنی طبقات بسته شده تحت الگوریتم های زیر)، زمانی که ما مطالعه کلاکی عرض. تا به امروز، تنها تعداد محدودی از کلاسهای حداقل ارثی از نمودارهای کاشی محدود نا محدود در ادبیات کشف شده است. در این مقاله، ما ثابت می کنیم که خانواده چنین کلاس ها بی نهایت است. علاوه بر این، ما نشان می دهیم که همین رابطه در رابطه با عرض کلاسی خطی درست است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
بی نهایت تعداد بسیار کم کلاس های گرافیکی از کلیدهای عرض نا محدود
چکیده انگلیسی
The celebrated theorem of Robertson and Seymour states that in the family of minor-closed graph classes, there is a unique minimal class of graphs of unbounded tree-width, namely, the class of planar graphs. In the case of tree-width, the restriction to minor-closed classes is justified by the fact that the tree-width of a graph is never smaller than the tree-width of any of its minors. This, however, is not the case with respect to clique-width, as the clique-width of a graph can be (much) smaller than the clique-width of its minor. On the other hand, the clique-width of a graph is never smaller than the clique-width of any of its induced subgraphs, which allows us to be restricted to hereditary classes (that is, classes closed under taking induced subgraphs), when we study clique-width. Up to date, only finitely many minimal hereditary classes of graphs of unbounded clique-width have been discovered in the literature. In the present paper, we prove that the family of such classes is infinite. Moreover, we show that the same is true with respect to linear clique-width.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 145-152
نویسندگان
, , , , ,