论文标题
在优先附件的色数上
On the chromatic number of the preferential attachment graph
论文作者
论文摘要
我们证明，在\ mathbb n $中的每一个$ m \ in（-m，0）$中的每一个$δ\，优先附件$ pa_t $ pa_t（m，δ）$的色数几乎肯定等于$ m+1 $。证明依赖于组合的组合构造的一系列色数$ m+1 $的挖掘物，其次是渐近地证明，几乎肯定会肯定有一个digraph，该家族被认为是优先附件图的子图。
We prove that for every $m\in \mathbb N$ and every $δ\in (-m,0)$, the chromatic number of the preferential attachment graph $PA_t(m, δ)$ is asymptotically almost surely equal to $m+1$. The proof relies on a combinatorial construction of a family of digraphs of chromatic number $m+1$ followed by a proof that asymptotically almost surely there is a digraph in this family, which is realised as a subgraph of the preferential attachment graph.
