...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Graphs and Combinatorics >On the b-Coloring of Cographs and P4-Sparse Graphs
【24h】

On the b-Coloring of Cographs and P4-Sparse Graphs

机译：关于Cograph和P 4 -稀疏图的b-着色

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

摘要

A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by χ b (G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is b-continuous if it admits a b-coloring with t colors, for every t = c(G), ¼, cb(G)t = chi(G), ldots, chi_b(G) . We define a graph G to be b-monotonic if χ b (H 1) ≥ χ b (H 2) for every induced subgraph H 1 of G, and every induced subgraph H 2 of H 1. In this work, we prove that P 4-sparse graphs (and, in particular, cographs) are b-continuous and b-monotonic. Besides, we describe a dynamic programming algorithm to compute the b-chromatic number in polynomial time within these graph classes.
机译：图的b着色是一种着色，以使每个颜色类别都允许一个顶点与至少一个顶点相邻，该顶点接收未分配给它的每种颜色。图G的b色数用χb（G）表示，是最大数t，因此G允许t色为b色。如果图G接受具有t种颜色的b色，则它是b连续的，对于每个t = c（G），¼，c b （G）t = chi（G），ldots， chi_b（G）。如果图χ b （H 1 ）≥χ b （H 2 ）对于G的每个诱导子图H 1 ，以及H 1 的每个诱导子图H 2 。在这项工作中，我们证明P 4 -稀疏图（尤其是cograph）是b连续和b单调的。此外，我们描述了一种动态规划算法来计算这些图类中多项式时间内的b色数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号