The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
复制标题
(theta、金字塔、1轮、3轮)无图的结构
DOI：
10.1002/jgt.22415
复制
发表时间：
2018
影响因子：
0.9
通讯作者：
Boncompagni V
中科院分区：
文献类型：
--
作者：
Boncompagni V
在本文中，我们研究了通过排除以下结构作为导出子图而定义的图类：θ，金字塔，1轮和3轮。我们在中描述了图的结构，并给出了这类图的多项式时间识别算法。我们还证明了中的自由图是4-可着色的。我们注意到它包括弦图类，以及无三角形图的线图类。
In this paper, we study the class of graphs defined by excluding the following structures as induced subgraphs: theta, pyramid, 1‐wheel, and 3‐wheel. We describe the structure of graphs in , and we give a polynomial‐time recognition algorithm for this class. We also prove that ‐free graphs in are 4‐colorable. We remark that includes the class of chordal graphs, as well as the class of line graphs of triangle‐free graphs.