首页> 外文会议>Graph-theoretic concepts in computer science >The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree
【24h】

The Complexity of Vertex Coloring Problems in Uniform Hypergraphs with High Degree

机译:高阶一致超图上顶点着色问题的复杂性

获取原文
获取原文并翻译 | 示例

摘要

In this note we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c_(r-1)~(∣V(H)-1∣),has a vertex 2-coloring and a strong vertex κ-coloring. Moti-vated by an old result of Edwards for graphs, we summarize what can be deduced from his method about the complexity of these problems for hy-pergraphs. We obtain the first optimal dichotomy results for 2-colorings of 3- and 4-uniform hypergraphs according to the value of c. In addi-tion, we determine the computational complexity of strong κ-colorings of 3-uniform hypergraphs for some c, leaving a gap which vanishes as k → ∞.
机译:在本说明中,我们考虑以下问题:确定给定的r-均匀超图H的最小顶点度至少为c_(r-1)〜(∣V(H)-1∣),是否具有2色顶点和强顶点κ着色。根据爱德华兹的旧结果作图,我们总结了从他的方法中可以得出的关于上图的这些问题的复杂性的结论。我们根据c的值获得了3和4均匀超图的2色的第一个最佳二分法结果。另外,对于某些c,我们确定了3个均匀超图的强κ着色的计算复杂度,留下的间隙随着k→∞而消失。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号