A note on local colorings of graphs (Q1356713): Difference between revisions

Let \(K(n,p)\) be the binomial random graph obtained from the complete graph \(K(n)\) by independent deletion of each edge with probability \(1-p\). An edge-coloring of a graph \(F\) is said to be \(r\)-local if at most \(r\) colors occur on the edges incident to any vertex of \(F\). \(F\rightarrow (G)_{r-loc}\) denotes the property that for every \(r\)-local coloring of the edges of \(F\) there is a monochromatic copy of \(G\).\ In this paper it is proved, among other things, that for all connected graphs \(G\) other than stars and for all integers \(r\geq 2\), there exist constants \(c\) and \(C\) such that \(\lim_{n\rightarrow \infty}P(K(n,p)\rightarrow (G)_{r-loc})\) equals 0 if \(p<cn^{-1/m_{G}}\) and 1 if \(p>Cn^{-1/m_{G}}\), where \(m_{G}= \max(|E(H)|-1)/(|V(H)|-2)\) and max is over all \(H\subseteq G\), \(|V(H)|\geq 3\), thus extending a previous result by \textit{V. Rödl} and the first author [J. Am. Math. Soc. 8, No. 4, 917-942 (1995; Zbl 0846.05079)].