论文标题
Burling图作为交叉图
Burling graphs as intersection graphs
论文作者
论文摘要
对于$ \ Mathbb r^d $的子集$ s $，$ s $ graphs是$ s $的特定转换的交点图。 Burling图的类别是一类无三角形图，具有任意较大的色数，在过去几年中引起了很多关注。 In 2012, Pawlik, Kozik, Krawczyk, Lasoń, Micek, Trotter, and Walczak showed that for every compact and path-connected set $ S \subseteq \mathbb R^2$ that is different from an axis-parallel rectangle, the class of $ S $-graphs contains all Burling graphs.但是，这两个类之间存在差距。近年来，了解与Burling图更接近或相等的$ s $ graphs的子类有所改善。在本文中，我们将对每个集合$ s $的差距与上述属性缩小：我们介绍了约束$ s $ graphs的类别，$ s $ graphs的子类，并证明它等于Burling Graphs类。我们还介绍了$ \ Mathbb r^2 $的子集的相交图的一组类别的图形类别，并证明它等于Burling图的类别。
For a subset $ S $ of $ \mathbb R^d$, $ S$-graphs are the intersection graphs of specific transformations of $ S $. The class of Burling graphs is a class of triangle-free graphs with arbitrarily large chromatic number that has attracted much attention in the last years. In 2012, Pawlik, Kozik, Krawczyk, Lasoń, Micek, Trotter, and Walczak showed that for every compact and path-connected set $ S \subseteq \mathbb R^2$ that is different from an axis-parallel rectangle, the class of $ S $-graphs contains all Burling graphs. There is, however, a gap between the two classes. In recent years, there have been improvements in understanding the subclasses of $ S $-graphs that are closer or equal to Burling graphs. In this article, we close this gap for every set $ S $ with the mentioned properties: we introduce the class of constrained $ S $-graphs, a subclass of $ S$-graphs, and prove that it is equal to the class of Burling graphs. We also introduce the class of constrained graphs, a subclass of intersection graphs of subsets of $ \mathbb R^2$, and prove that it is equal to the class of Burling graphs.
