کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903494 | 1632569 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Clique cutsets beyond chordal graphs
ترجمه فارسی عنوان
کلاکت های فراتر از نمودارهای هوستر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کلک، مجموعه پایدار رنگ ارغوانی، ساختار، الگوریتم ها،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. We also obtain polynomial Ï-bounding functions for these classes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 81-86
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 81-86
نویسندگان
Valerio Boncompagni, Irena Penev, Kristina VuÅ¡koviÄ,