کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420083 | 683892 | 2012 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
2K22K2-partition of some classes of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the problem of partitioning the vertex-set of a graph into four non-empty sets A,B,C,DA,B,C,D such that every vertex of AA is adjacent to every vertex of BB and every vertex of CC is adjacent to every vertex of DD. The complexity of deciding if a graph admits such a partition is unknown. We show that it can be solved in polynomial time for several classes of graphs: K4K4-free graphs, diamond-free graphs, planar graphs, graphs with bounded treewidth, claw-free graphs, (C5,P5)(C5,P5)-free graphs and graphs with few P4P4’s.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 18, December 2012, Pages 2662–2668
Journal: Discrete Applied Mathematics - Volume 160, Issue 18, December 2012, Pages 2662–2668
نویسندگان
Simone Dantas, Frédéric Maffray, Ana Silva,