کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949900 | 1364262 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterization and recognition of some opposition and coalition graph classes
ترجمه فارسی عنوان
شناسایی و شناخت بعضی از کلاس های گرافیکی مخالف و ائتلاف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار کاملا قابل سفارش نمودار یک در یک، نمودار اپوزیسیون گراف ائتلاف، گراف کامل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A graph is an opposition graph, respectively, a coalition graph, if it admits an acyclic orientation which puts the two end-edges of every chordless 4-vertex path in opposition, respectively, in the same direction. Opposition and coalition graphs have been introduced and investigated in connection to perfect graphs. Recognizing and characterizing opposition and coalition graphs are long-standing open problems. This paper gives characterizations for opposition graphs and coalition graphs on some restricted graph classes. Implicit in our arguments are polynomial time recognition algorithms for these graphs. We also give a good characterization for the so-called generalized opposition graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 261-272
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 261-272
نویسندگان
Van Bang Le, Thomas Podelleck,