• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议> >Choosability in coloring problems of graphs with restricted color lists
【24h】

Choosability in coloring problems of graphs with restricted color lists

机译：颜色列表受限制的图形在着色问题中的选择能力

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

摘要

In this paper we present a correlation between a variation of the list problem coloring in graphs, the (γ, μ)-coloring, and the property of choosability in graphs, resulting in the k-(γ, μ)-choosability. The list coloring problem is a variation of the classical vertex coloring problem, introduced by Erdos et al. in 1979, along with a property very studied in list coloring: the choosability in graphs. In this work, algorithms were developed to determine the k-choosability and the k-(γ, μ)-choosability of a general simple graph, and a greedy heuristic based on DSATUR. In addition, we applied special techniques to prove the property of choosability in some classes of graphs, involving a general proof for simple graphs, which guarantees that if a graph is k-colorable it is also k-(γ, μ)-choosable, being the computational complexity reduced from the class Πp2-complete to the NP-complete.
机译：在本文中，我们提出了图表中列表问题颜色的变化，（γ，μ）着色和图表中选择性的性质之间的相关性，从而导致了k-（γ，μ）选择性。列表着色问题是Erdos等人介绍的经典顶点着色问题的变体。 1979年，以及一项针对列表着色进行了深入研究的特性：图形的选择性。在这项工作中，开发了确定通用简单图的k选择性和k-（γ，μ）选择性以及基于DSATUR的贪婪启发式算法。此外，我们应用了特殊的技术来证明某些类型图的选择性，其中包括对简单图的一般证明，这保证了如果图是可k着色的，那么它也是k-（γ，μ）可选的，计算复杂度从Π p 2 -完全降低到NP-complete。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号