论文标题
在边缘颜色的简单图纸$ k_n $中跨越树木的飞机
Plane Spanning Trees in Edge-Colored Simple Drawings of $K_n$
论文作者
论文摘要
Károlyi，Pach和Tóth证明，完整图的每2层直线图都包含一个单色平面跨越树。如果此语句将其推广到其他类别的图纸，则是打开的，特别是将完整图的简单图纸。这些图纸是边缘由约旦弧表示的图纸，其中任何两个最多一次相交。我们为这样的概括提供了两个部分结果。首先，我们证明该语句适用于圆柱形简单图纸。 （在圆柱形图中，所有顶点都放在两个同心圆，没有边缘的圆圈上。在这种情况下，我们表明每$ \ lceil（n+5）/6 \ rceil $ - edge色彩的单调$ k_n $的简单图包含一个跨度平面跨越树。 （在单调图中，每个边缘都表示为$ x $单子酮曲线。）
Károlyi, Pach, and Tóth proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $\lceil (n+5)/6\rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)
