کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419512 683825 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Facet-inducing web and antiweb inequalities for the graph coloring polytope
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Facet-inducing web and antiweb inequalities for the graph coloring polytope
چکیده انگلیسی

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
نویسندگان
,