Clique-cutsets beyond chordal graphs
Clique-cutsets beyond chordal graphs
复制标题
弦图之外的集团割集
DOI：
10.1002/jgt.22428
复制
发表时间：
2018
影响因子：
0.9
通讯作者：
Boncompagni V
中科院分区：
文献类型：
--
作者：
Boncompagni V
Truemper构形（θ、金字塔、棱镜和轮子）在复杂遗传图类（如完美图类和无偶孔图类）的研究中发挥了重要作用，它们既可以作为排除的构形出现，也可以作为图可以分解的构形出现。在本文中，我们研究了（作为诱导子图）除了（可能）万向轮和双轮外不包含Truemper构型的图的结构。我们还研究了这个类的几个子类。我们使用我们的结构结果来分析这些类的识别复杂性、最大权团、最大权稳定集和最优顶点着色问题。进一步，我们得到了这些类的多项式边界函数。
Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (eg, the class of perfect graphs and the class of even‐hole‐free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. Furthermore, we obtain polynomial ‐bounding functions for these classes.