论文标题
定向的界限的色度图
The oriented chromatic number of random graphs of bounded degree
论文作者
论文摘要
随机图$ \ Mathcal {g}（n，p）$的色数长期以来一直研究过，并启发了几个地标结果。在$ p = d/n $的情况下，achlioptas和naor表明，色数渐近地集中在$ k_d $或$ k_d+1 $的情况下，其中$ k_d $是最小的整数，因此$ d <2k_d \ log log log k_d $。 Kemkes等。后来证明了相同的结果适用于$ \ mathcal {g}（n，d）$，随机$ d $ - regular Graph。我们考虑定向模型的定向色数$ \ vec {\ Mathcal {g}}}（n，p）$和$ \ vec {\ Mathcal {g}}}（n，d）$，改善了从$ o（d^2^d）$ o（d^2^d）$ o（d^2^d）$（d^2^d）$（d^2^d）$（d^2^d）$（
The chromatic number of the random graph $\mathcal{G}(n,p)$ has long been studied and has inspired several landmark results. In the case where $p = d/n$, Achlioptas and Naor showed the chromatic number is asymptotically concentrated at $k_d$ or $k_d+1$, where $k_d$ is the smallest integer such that $d < 2k_d\log k_d$. Kemkes et al. later proved the same result holds for $\mathcal{G}(n,d)$, the random $d$-regular graph. We consider the oriented chromatic number of the directed models $\vec{\mathcal{G}}(n,p)$ and $\vec{\mathcal{G}}(n,d)$, improving the best known upper bound from $O(d^2 2^d)$ to $O(\sqrt{e}^d)$.
