The chromatic-number conjecture for preferential attachment graphs

Let PAt(m,δ)PA_t(m,\delta) be the preferential attachment graph at time tt, with parameters mm and δ\delta, and let (PAt(m,δ))t1(PA_t(m,\delta))_{t\ge 1} denote the resulting graph sequence. The chromatic-number conjecture. For every m1m\ge 1 and every δ>m\delta>-m, the chromatic number of (PAt(m,δ))t1(PA_t(m,\delta))_{t\ge 1} converges almost surely to m+1m+1. This extends the proved result for δ(m,0)\delta\in(-m,0) and asks whether the same limiting behavior holds throughout the range δ>m\delta>-m; the case τ3\tau\ge 3 is identified as an open direction in the paper.

Sources & referencesView supporting material

Primary source

Lyuben Lichev, “On the chromatic number of the preferential attachment graph”, arXiv:2008.00871 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.