...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the Grundy number of graphs with few ~(P 4)'s
【24h】

On the Grundy number of graphs with few ~(P 4)'s

机译：关于极少〜（P 4）的图的Grundy数

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

摘要

The Grundy number of a graph G is the largest number of colors used by any execution of the greedy algorithm to color G.The problem of determining the Grundy number of G is polynomial if G is a ~(P4)-free graph and NP-hard if G is a ~(P5)-free graph.In this article, we define a new class of graphs, the fat-extended P4-laden graphs, and we show a polynomial time algorithm to determine the Grundy number of any graph in this class.Our class intersects the class of ~(P5)-free graphs and strictly contains the class of ~(P4)-free graphs.More precisely, our result implies that the Grundy number can be computed in polynomial time for any graph of the following classes: ~(P4)-reducible, extended ~(P4)-reducible, ~(P4)-sparse, extended ~(P4)-sparse, ~(P4)-extendible, ~(P4)-lite, ~(P4)-tidy, ~(P4)-laden and extended ~(P4)-laden, which are all strictly contained in the fat-extended ~(P4)-laden class.
机译：图G的Grundy数是任何执行贪婪算法为G着色所使用的最大颜色数。如果G是无〜（P4）图且NP-，则确定G的Grundy数的问题是多项式。如果G是不含〜（P5）的图，则很难。在本文中，我们定义了一类新的图，即脂肪扩展的P4负载图，并且我们展示了多项式时间算法来确定图中任何图的Grundy数。我们的类与〜（P5）-无图的图类相交，并且严格包含〜（P4）-无图的图类。更准确地说，我们的结果表明可以对多项式的任意图在多项式时间内计算Grundy数。下列类别：〜（P4）可归约，扩展〜（P4）可归约，〜（P4）-稀疏，扩展〜（P4）-稀疏，〜（P4）-可扩展，〜（P4）-lite，〜（ P4）-整洁，〜（P4）-负载和扩展〜（P4）-负载，它们都严格包含在脂肪扩展的〜（P4）-负载类中。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号