On the Chromatic Number of Disjointness Graphs of Curves
On the Chromatic Number of Disjointness Graphs of Curves
复制标题
关于曲线不相交图的色数
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
István Tomon
中科院分区：
文献类型：
--
作者：
J. Pach;István Tomon
设$omega(G)$和$chi(G)$分别表示图$G$的团数和色数。曲线族（平面上连续的弧）的{em不相交图}是其顶点对应于曲线的图，其中两个顶点由一条边连接当且仅当相应的曲线是不相交的。如果每条垂直线与曲线相交至多一个点，则曲线称为{em $x$-单调}。如果$x$-单调曲线的左端点位于$y$-轴上，则该曲线为{em接地}。
Let $omega(G)$ and $chi(G)$ denote the clique number and chromatic number of a graph $G$, respectively. The {em disjointness graph} of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called {em $x$-monotone} if every vertical line intersects it in at most one point. An $x$-monotone curve is {em grounded} if its left endpoint lies on the $y$-axis.
We prove that if $G$ is the disjointness graph of a family of grounded $x$-monotone curves such that $omega(G)=k$, then $chi(G)leq inom{k+1}{2}$. If we only require that every curve is $x$-monotone and intersects the $y$-axis, then we have $chi(G)leq frac{k+1}{2}inom{k+2}{3}$. Both of these bounds are best possible. The construction showing the tightness of the last result settles a 25 years old problem: it yields that there exist $K_k$-free disjointness graphs of $x$-monotone curves such that any proper coloring of them uses at least $Omega(k^{4})$ colors. This matches the upper bound up to a constant factor.