کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419512 | 683825 | 2010 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Facet-inducing web and antiweb inequalities for the graph coloring polytope
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
For a graph GG and its complement Ḡ, we define the graph coloring polytope P(G)P(G) to be the convex hull of the incidence vectors of star partitions of Ḡ. We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in GG. We show that for an antiweb W̄ in GG the corresponding inequality is facet-inducing for P(G)P(G) if and only if W̄ is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 18, 28 November 2010, Pages 2075–2080
Journal: Discrete Applied Mathematics - Volume 158, Issue 18, 28 November 2010, Pages 2075–2080
نویسندگان
Gintaras Palubeckis,