论文标题
平面图的渐近最佳顶点排名
Asymptotically Optimal Vertex Ranking of Planar Graphs
论文作者
论文摘要
a（vertex）$ \ ell $ - lanking是一种着色$φ：v（g）\ to \ mathbb {n} $带有整数颜色的图$ g $的顶点$φ（u_0）<\ max \ {φ（u_0），\ ldots，φ（u_p）\} $。我们表明，对于任何固定的整数$ \ ell \ ge 2 $，每个$ n $ vertex planar graph都具有$ \ ell $ - 使用$ o（\ log n/\ log \ log \ log \ log \ log \ log n）$颜色，即使$ \ ell = ell = 2 $，也很紧；对于无限的$ n $值，有$ n $ vertex平面图，任何2级都需要$ω（\ log n/\ log \ log \ log \ log \ log n）$颜色。该结果还扩展到有界的属图。 在开发此证明时，我们获得了$ \ ell $ lanking treewidth $ t $所需的颜色数量的最佳界限以及简单的TreeWidth $ t $的图。这些上限是建设性的，并给出$ O（N）$ - 时间算法。我们技术带来的其他结果包括新的Sublogarithmic上限，对$ \ ell $ - Apex次要的无少量图和$ K $ - $ - 平面图所需的颜色数量。
A (vertex) $\ell$-ranking is a colouring $φ:V(G)\to\mathbb{N}$ of the vertices of a graph $G$ with integer colours so that for any path $u_0,\ldots,u_p$ of length at most $\ell$, $φ(u_0)\neqφ(u_p)$ or $φ(u_0)<\max\{φ(u_0),\ldots,φ(u_p)\}$. We show that, for any fixed integer $\ell\ge 2$, every $n$-vertex planar graph has an $\ell$-ranking using $O(\log n/\log\log\log n)$ colours and this is tight even when $\ell=2$; for infinitely many values of $n$, there are $n$-vertex planar graphs, for which any 2-ranking requires $Ω(\log n/\log\log\log n)$ colours. This result also extends to bounded genus graphs. In developing this proof we obtain optimal bounds on the number of colours needed for $\ell$-ranking graphs of treewidth $t$ and graphs of simple treewidth $t$. These upper bounds are constructive and give $O(n)$-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for $\ell$-rankings of apex minor-free graphs and $k$-planar graphs.
