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
    0 references
    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
    0 references
    Ramsey property
    0 references
    random graph
    0 references
    \(r\)-edge coloring
    0 references
    star graph
    0 references

    Identifiers