• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope
【24h】

Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope

机译：代表k折叠着色多态性的解除，投影和子图引起的不等式

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A k-fold x-coloring of a graph G is an assignment of (at least) k distinct colors from the set {1, 2,..., x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The kth chromatic number of G, denoted by chi(k)(G), is the smallest x such that G admits a k-fold x-coloring. We present an integer linear programming formulation (ILP) to determine chi(k) (G) and study the facial structure of the corresponding polytope P-k (G). We show facets that Pk+1(G) inherits from P-k(G) and show how to lift facets from P-k (G) to Pk+l (G). We project facets of P-1 (G o K-k) into facets of P-k (G), where G o K-k is the lexicographic product of G by a clique with k vertices. In both cases, we can obtain facet-defining inequalities from many of those known for the 1-fold coloring polytope. We also derive facets of P-k (G) from facets of stable set polytopes of subgraphs of G. In addition, we present classes of facet-defining inequalities based on strongly chi(k)-critical webs and antiwebs, which extend and generalize known results for 1-fold coloring. We introduce this criticality concept and characterize the webs and antiwebs having such a property. (C) 2016 Elsevier B.V. All rights reserved.
机译：图G的k倍x着色是将至少{{，2，...，x}}组中的至少k种不同颜色分配给每个顶点，以便将任意两个相邻顶点分配为不相交的颜色。 G的第k个色数由chi（k）（G）表示，是最小的x，因此G允许进行k倍的x着色。我们提出一种整数线性规划公式（ILP）来确定chi（k）（G），并研究相应多位点P-k（G）的面部结构。我们展示了Pk + 1（G）继承自P-k（G）的方面，并展示了如何将方面从P-k（G）提升到Pk + 1（G）。我们将P-1（G o K-k）的面投影到P-k（G）的面中，其中G o K-k是G的词法乘积，带有k个顶点。在这两种情况下，我们都可以从许多已知的1倍着色多表位获得不平等的方面。我们还从G的子图的稳定集多边形的刻面衍生出Pk（G）的刻面。此外，我们基于强chi（k）临界网和反网提出了定义刻面的不等式类别，这些不等式扩展并概括了已知结果用于1色着色。我们介绍此临界概念并表征具有这种特性的纤维网和反纤维网。 （C）2016 Elsevier B.V.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号