(Theta, triangle)‐free and (even hole, K 4 )‐free graphs—Part 1: Layered wheels
(Theta, triangle)‐free and (even hole,
K
4 )‐free graphs—Part 1: Layered wheels
复制标题
（Theta，三角形）无且（偶孔，K
DOI：
--
复制
发表时间：
2019
影响因子：
0.9
通讯作者：
Nicolas Trotignon
中科院分区：
文献类型：
--
作者：
Ni Luh Dewi Sintiari;Nicolas Trotignon
我们提出了一种称为分层轮子的结构。分层轮子是任意大的树宽和周长的曲线图。它们可能是一个可能的定理的结果，该定理用导出子图来刻画具有大树宽的图(虽然这样的刻画在子图方面是很好地理解的)。它们还给出了研究较好的类中的大树宽和大阶宽的图的例子，例如无(角)图和无偶洞图(其中洞是长度至少为4的无弦圈，角是由至少两个连接两个顶点的三条内部顶点不相交的路组成的图，而K4是四个顶点上的完全图)。
We present a construction called layered wheel. Layered wheels are graphs of arbitrarily large treewidth and girth. They might be an outcome for a possible theorem characterizing graphs with large treewidth in terms of their induced subgraphs (while such a characterization is well‐understood in terms of minors). They also provide examples of graphs of large treewidth and large rankwidth in well‐studied classes, such as (theta, triangle)‐free graphs and even‐hole‐free graphs with no K 4 (where a hole is a chordless cycle of length at least four, a theta is a graph made of three internally vertex disjoint paths of length at least two linking two vertices, and K 4 is the complete graph on four vertices).
关于偶无洞图的秩宽度
DOI：
10.48550/arxiv.1611.09907
发表时间：
2016
期刊：
arXiv e-prints
影响因子：
--
作者：
Adler Isolde
通讯作者：
Adler Isolde