Indexed by:
Abstract:
For graphs G and H, let G→ (H, H) signify that any red/blue edge coloring of G contains a monochromatic H as a subgraph. Denote H(Δ , n) = { H: | V(H) | = n, Δ (H) ≤ Δ }. For any Δ and n, we say that G is partition universal for H(Δ , n) if G→ (H, H) for every H∈ H(Δ , n). Let Gr(N, p) be the random spanning subgraph of the complete r-partite graph Kr(N) with N vertices in each part, in which each edge of Kr(N) appears with probability p independently and randomly. We prove that for fixed Δ ≥ 2 there exist constants r, B and C depending only on Δ such that if N≥ Bn and p= C(log N/ N) 1 / Δ, then asymptotically almost surely Gr(N, p) is partition universal for H(Δ , n). © 2017, Springer Science+Business Media, LLC, part of Springer Nature.
Keyword:
Reprint 's Address:
Email:
Source :
Journal of Combinatorial Optimization
ISSN: 1382-6905
Year: 2018
Issue: 3
Volume: 35
Page: 724-739
0 . 8 1 6
JCR@2018
0 . 9 0 0
JCR@2023
ESI HC Threshold:68
JCR Journal Grade:3
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count: 5
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: