A note on local colorings of graphs (Q1356713): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(96)00058-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2133985202 / rank | |||
Normal rank |
Latest revision as of 08:31, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on local colorings of graphs |
scientific article |
Statements
A note on local colorings of graphs (English)
0 references
14 August 1997
0 references
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)].
0 references
Ramsey property
0 references
random graph
0 references
\(r\)-edge coloring
0 references
star graph
0 references