List chromatic number of the square of a sparse random graph.
This paper is about colouring the square of an (Erdős-Rényi) random graph \(G(n,p)\). Recall that the square \(G^2\) of a graph \(G=(V,E)\) has vertex set \(V\) with two vertices being adjacent in \(G^2\) if and only if they are at distance at most 2 in \(G\). The range of \(p\) considered in this paper is the sparse case where \(p=c/n\) for a positive constant \(c\) (below we note \(c\) can in fact be allowed to grow slowly).\N\NThe main result relates to the list chromatic number. Recall that for a graph \(G=(V,E)\) the list chromatic number \(\chi_{\ell}(G)\) is the smallest \(k\) such that, whatever lists of colours \(L(v)\) with \(\vert L(v)\vert =k\) are assigned to every \(v\in V\), there is a proper colouring of \(G\) with every vertex taking a colour from its list. As one of the possibilities for lists of size \(k\) is \(L(v)=\{1,2,\ldots, k\}\ \forall v\in V\), we see that \(\chi_{\ell}(G)\geq \chi(G)\). The naive initial hope that having more colours might make clash avoidance easier and force \(\chi_{\ell}(G)=\chi(G)\) is wrong; for example the complete bipartite graph \(H=K_{t,t}\) has chromatic number \(\chi(H)=2\) but \(\chi_{\ell}(H)\) is about \(\ln(t)\).\N\NA lower bound for the clique number (and hence also chromatic number) of \(G^{2}\) is the maximum degree \(\Delta(G)\) of \(G\), as the neighbours (in \(G\)) of a vertex of maximum degree form a clique in \(G^{2}\). The main result of the paper under review is that, using \(G_2\) to denote the square of \(G(n,c/n)\), this easy lower bound on \(\chi_{\ell}(G_2)\) is asymptotically correct: with \(p=c/n\) as above, we have whp (i.e. with probability tending to 1 as \(n\rightarrow\infty\)) that \(\chi_{\ell}(G_2)=(1+o(1))\Delta(G(n,c/n))\). This, of course, also means that the chromatic number and clique number asymptotically take this value. Note that the maximum degree of \(G(n,c/n)\) is whp asymptotically \(\ln(n)/\ln\ln(n)\) irrespective of the value of the constant \(c\).\N\NIn fact, the authors note that their techniques can be extended to prove a similar result when \(c\) is not required to be constant but is allowed to grow slowly with \(n\); it will work for \(c(n)=o(\ln\ln(n))\).\N\NA little flavour of the result is perhaps conveyed by saying that it depends on a greedy colouring of the vertices in a carefully chosen order; first, vertices of high degree, then vertices adjacent to vertices of high degree, then all remaining vertices\N\NThe authors mention some directions for further work, noting, for example, that the list chromatic number of the square of \(G(n,c/n)\) could be as low as \(\Delta(G(n,c/n)) +1\) though they are not confident that this is true. They also note the possibility of considering higher powers rather than just the square: they have recently proved a result which may be relevant to this, by showing that the maximum degree of the \(r\)th power of \(G(n,c/n)\) for positive constant \(c\) is \(\ln(n)/\ln_{r+1}(n)\) in the preprint [the authors, ``The maximum degree of the \(r\)th power of a sparse random graph, Preprint, \url{arXiv:2404.06410}]. Here \(\ln_{k}(n)\) denotes the \(k\)-fold iterated natural logarithm of \(n\).
This page was built for publication: List chromatic number of the square of a sparse random graph.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858185)
