Zobrazeno 1 - 3
of 3
pro vyhledávání: '"Raut, Aditya"'
Autor:
Frieze, Alan, Raut, Aditya
Let $G^r_{n,p}$ denote the $r$th power of the random graph $G_{n,p}$, where $p=c/n$ for a positive constant $c$. We prove that w.h.p. the maximum degree $\Delta\left(G^r_{n,p}\right)\sim \frac{\log n}{\log_{(r+1)}n}$. Here $\log_{(k)}n$ indicates the
Externí odkaz:
http://arxiv.org/abs/2404.06410
Autor:
Frieze, Alan, Raut, Aditya
We show that w.h.p the chromatic number $\chi$ of the square of $G_{n,p},p=c/n$ is asymptotically equal to the maximum degree $\Delta(G_{n,p})$. This improves an earlier result of Garapaty et al \cite{KLMP} who proved that $\chi(G^2_{n,p})=\Theta \le
Externí odkaz:
http://arxiv.org/abs/2312.03563
Publikováno v:
Journal of Failure Analysis & Prevention; Oct2023, Vol. 23 Issue 5, p1980-1990, 11p
