论文标题
使用硬币模型来界定平面图的广义着色数
Bounding generalized coloring numbers of planar graphs using coin models
论文作者
论文摘要
我们研究了平面图的Koebe顺序：通过将图形建模为平面中成对内部旋转盘的相交图获得的顶点顺序，并通过对相关圆盘的非侵蚀半径进行订购顶点。我们证明，对于\ mathbb {n} $中的每$ d \ in，任何此类订购都具有$ d $ - 加热性，由$ o（d/\ ln d）$和弱$ d $ - 颜色的数字由$ o（d^4 \ ln d）限制。这尤其表明，平面图的$ d $ - 可加权性受$ O（d/\ ln d）$界限，该$渐近与由于dvoDemank和siebertz造成的已知下限匹配。
We study Koebe orderings of planar graphs: vertex orderings obtained by modelling the graph as the intersection graph of pairwise internally-disjoint discs in the plane, and ordering the vertices by non-increasing radii of the associated discs. We prove that for every $d\in \mathbb{N}$, any such ordering has $d$-admissibility bounded by $O(d/\ln d)$ and weak $d$-coloring number bounded by $O(d^4 \ln d)$. This in particular shows that the $d$-admissibility of planar graphs is bounded by $O(d/\ln d)$, which asymptotically matches a known lower bound due to Dvořák and Siebertz.
