...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Total chromatic number of unichord-free graphs
【24h】

Total chromatic number of unichord-free graphs

机译：无双曲线图的总色数

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

摘要

A unichord is an edge that is the unique chord of a cycle in a graph. The class C of unichord-free graphs that is, graphs that do not contain, as an induced subgraph, a cycle with a unique chord was recently studied by Trotignon and Vukovi (2010) [24], who proved strong structure results for these graphs and used these results to solve the recognition and vertex-colouring problems. Machado et al. (2010) [18] determined the complexity of the edge-colouring problem in the class C and in the subclass ~(C′) obtained from C by forbidding squares. In the present work, we prove that the total-colouring problem is NP-complete when restricted to graphs in C. For the subclass ~(C′), we establish the validity of the Total Colouring Conjecture by proving that every non-complete square, unichord-free graph of maximum degree at least 4 is Type 1.
机译：单弦是指图中循环的唯一弦的边。 Trotignon和Vukovi（2010）最近研究了无无向图的C类，即不包含作为诱导子图的具有唯一弦的周期的图[24]，他们证明了这些图的强大结构结果并使用这些结果来解决识别和顶点着色问题。 Machado等。 （2010）[18]确定了在C类和禁止C的子类〜（C'）中边缘着色问题的复杂性。在目前的工作中，我们证明了当只限于C中的图时，总着色问题是NP完全的。对于子类〜（C'），我们通过证明每个不完整的正方形来建立总着色猜想的有效性，最大度至少为4的无环图是类型1。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号