• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring
【24h】

The (theta, wheel)-free graphs Part III: Cliques, stable sets and coloring

机译：（θ，车轮） - 免费图第III部分：Cliques，稳定的组和着色

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

摘要

A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three paths between the same pair of distinct vertices so that the union of any two of the paths induces a hole. A wheel is a graph formed by a hole and a vertex that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins, and consequently obtain a polynomial time recognition algorithm for the class. In this paper we further use this decomposition theorem to obtain polynomial time algorithms for maximum weight clique, maximum weight stable set and coloring problems. We also show that for a graph G in the class, if its maximum clique size is omega, then its chromatic number is bounded by max {omega, 3}, and that the class is 3-clique-colorable. Crown Copyright (C) 2019 Published by Elsevier Inc. All rights reserved.
机译：图中的一个孔是长度至少4的弦循环。θ是由相同的不同顶点之间的三个路径形成的曲线图，使得任何两个路径的联合引起孔。车轮是由孔和顶点形成的曲线图，顶点在孔中具有至少3个邻居。在这一系列论文中，我们研究了不包含作为诱导的子图的图表中的图表，也不包含轮子。在该系列的第二部分中，我们证明了这种类的分解定理，它使用Clique剪切和2-联接，因此获得了类的多项式时间识别算法。在本文中，我们进一步使用该分解定理来获得多项式时间算法，以获得最大重量的集团，最大重量稳定集和着色问题。我们还表明，对于类中的图形g，如果其最大Clique大小是Omega，则其色度由Max {Omega，3}界定，并且该类是3-Clique可色。 2019年Elsevier Inc.版权所有的皇家版权（c）2019年保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号