• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Partial characterizations of clique-perfect and coordinated graphs:Superclasses of triangle-free graphs
【24h】

Partial characterizations of clique-perfect and coordinated graphs:Superclasses of triangle-free graphs

机译：完美集团图和协调图的部分特征：无三角形图的超类

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

摘要

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of Hequals the cardinality of a minimum clique-transversal of H, for every induced subgraphH of G. A graph G is coordinated if the minimum number of colors that can be assigned tothe cliques of H in such a way that no two cliques with non-empty intersection receivethe same color equals the maximum number of cliques of H with a common vertex, forevery induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. Thecomplete lists of minimal forbidden induced subgraphs for the classes of clique-perfectand coordinated graphs are not known, but some partial characterizations have beenobtained. In this paper, we characterize clique-perfect and coordinated graphs by minimalforbidden induced subgraphs when the graph is either paw-free or (gem, W4, bull}-free,both superclasses of triangle-free graphs
机译：如果对图G的每个诱导子图H，最大图独立的集合He的基数等于H的最小图面遍历的基数，则图G是图群完美的。分配给H的派系，使得没有两个非空相交的派系不会收到相同的颜色等于具有相同顶点的H的派系的最大数量，这是G的永远归纳的子图H。 。目前尚不知道关于集团完美和协调图类的最小禁止诱导子图的完整列表，但是已经获得了一些部分特征。在本文中，当图是无爪或无（gem，W4，bull），都是无三角图的超类时，我们通过极小禁止的诱导子图来表征群体完美图和协调图

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号