The Burling sequence is a sequence of triangle-free graphs of increasing chromatic number. Each of them is isomorphic to the intersection graph of a set of axis-parallel boxes in $R^3$. These graphs were also proved to have other geometrical representations: intersection graphs of line segments in the plane, and intersection graphs of frames, where a frame is the boundary of an axis-aligned rectangle in the plane. We call Burling graph every graph that is an induced subgraph of some graph in the Burling sequence. We give five new equivalent ways to define Burling graphs. Three of them are geometrical, one is of a more graph-theoretical flavour and one is more axiomatic.
翻译:交错序列是三角无三角图的序列, 增加色谱数。 每张图都是以$R$3美元表示的一组轴- 平行框的交叉图。 这些图表还被证明具有其他几何表示: 平面线段的交叉图, 和框架的交叉图, 其中框是平面轴对齐矩形的边界。 我们将每张图都称为伯林图的引导子图。 我们给出了五个新的等同方法来定义布林图。 其中三个是几何图, 一个是更图形- 理论波纹, 一个是更不言理的。