کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649498 1342458 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On facets of stable set polytopes of claw-free graphs with stability number 3
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On facets of stable set polytopes of claw-free graphs with stability number 3
چکیده انگلیسی

Obtaining a complete description of the stable set polytopes of claw-free graphs is a long-standing open problem. Eisenbrand et al. recently achieved a breakthrough for the subclass of quasi-line graphs. As a consequence, every non-trivial facet of their stable set polytope has at most two different, but arbitrarily high left hand side coefficients. For the graphs with stability number 2, Cook showed that all their non-trivial facets are 1/2-valued. For claw-free but not quasi-line graphs with stability number at least 4, Stauffer conjectured that the same holds true. In contrast, there are known claw-free graphs with stability number 3 which induce facets with up to eight different left hand side coefficients. We prove that the situation is even worse: for every positive integer bb, we exhibit a claw-free graph with stability number 3 inducing a facet with bb different left hand side coefficients.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 3, 6 February 2010, Pages 493–498
نویسندگان
, ,