Hasse diagrams with large chromatic number
Hasse diagrams with large chromatic number
复制标题
大色数哈斯图
DOI：
10.1112/blms.12457
复制
发表时间：
2021
影响因子：
0.9
通讯作者：
Tomon, István
中科院分区：
文献类型：
--
作者：
Suk, Andrew;Tomon, István
对于每一个正整数，我们构造了一个有顶点和独立数的Hasse图.这样的图有色数，这大大改进了以前最著名的具有色数的Hasse图的构造。此外，如果我们还要求围长至少，我们构造这样的Hasse图的独立数最多。这些证明是基于在平面上有许多关联的点-线排列的存在性，并且避免了我们发现的某些独立感兴趣的禁用子配置。这些结果也有以下令人惊讶的几何后果。它们意味着在平面上存在一个曲线族，使得的不交图是无三角形的（或具有高围长），但的色数是多项式。同样，由于Pach，Tardos和Tóth，以前最著名的构造只有对数色数。
For every positive integer, we construct a Hasse diagram withvertices and independence number. Such graphs have chromatic number, which significantly improves the previously best‐known constructions of Hasse diagrams having chromatic number. In addition, if we also require girth of at least, we construct such Hasse diagrams with independence number at most. The proofs are based on the existence of point‐line arrangements in the plane with many incidences and avoids certain forbidden subconfigurations, which we find of independent interest.These results also have the following surprising geometric consequence. They imply the existence of a familyofcurves in the plane such that the disjointness graphofis triangle‐free (or has high girth), but the chromatic number ofis polynomial in. Again, the previously best‐known construction, due to Pach, Tardos and Tóth, had only logarithmic chromatic number.
登录
查看更多内容
DOI：
10.1016/j.jctb.2010.01.003
发表时间：
2010-09
期刊：
J. Comb. Theory B
影响因子：
--
作者：
A. Kostochka;P. Pudlák;V. Rödl
通讯作者：
A. Kostochka;P. Pudlák;V. Rödl
线段的不相交图
DOI：
--
发表时间：
2017
期刊：
International Symposium on Computational Geometry
影响因子：
--
作者：
J. Pach;G. Tardos;G. Tóth
通讯作者：
G. Tóth
影响因子：
0.8
作者：
A. Gyárfás
通讯作者：
A. Gyárfás
DOI：
--
发表时间：
1991
期刊：
影响因子：
--
作者：
I. Kríz;J. Nesetril
通讯作者：
J. Nesetril
DOI：
--
发表时间：
2018
期刊：
International Symposium on Computational Geometry
影响因子：
--
作者：
J. Pach;István Tomon
通讯作者：
István Tomon