论文标题
关于凸几何和有序图的渐近填料
On asymptotic packing of convex geometric and ordered graphs
论文作者
论文摘要
如果在完整的凸面几何图中存在$ g $的$ g $，则凸出的几何图$ g $可以包装。我们证明，每个凸面几何图最多可包装$ 4 $。有了相似的有序图形包装性定义，我们证明每个有订购的图形最多$ 3 $都可以包装。基于平均长度的争论表明这些结果是最好的。我们还确定了由于具有许多“长”边缘而可包装的一类凸几何图。
A convex geometric graph $G$ is said to be packable if there exist edge-disjoint copies of $G$ in the complete convex geometric graph $K_n$ covering all but $o(n^2)$ edges. We prove that every convex geometric graph with cyclic chromatic number at most $4$ is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most $3$ is packable. Arguments based on the average length of edges imply these results are best possible. We also identify a class of convex geometric graphs that are packable due to having many "long" edges.
