On the chromatic number of the preferential attachment graph

Abstract

We prove that for every $m\in \mathbb{N}$ and every $\delta \in (-m,0)$, the chromatic number of the preferential attachment graph $P{A}_t(m,\delta )$ 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.

14 pages, 3 figures