کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652645 1632594 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Near-perfect graphs with polyhedral N+(G)
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Near-perfect graphs with polyhedral N+(G)
چکیده انگلیسی

One of the beautiful results due to Grötschel, Lovász and Schrijver is the fact that the theta body of a graph G is polyhedral if and only if G is perfect. Related to the theta body of G is a foundational construction of an operator on polytopes, called N+(⋅), by Lovász and Schrijver. Here, we initiate the pursuit of a characterization theorem analogous to the one above by Grötschel, Lovász and Schrijver, replacing the theta body of G by N+(G) and searching for the combinatorial counterpart to replace the class of perfect graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 393-398