Indexed by:
Abstract:
A graph H= (W, EH) is said to have bandwidth at most b if there exists a labeling of W as w1, w2, ⋯ , wn such that | i- j| ≤ b for every edge wiwj∈ EH. We say that H is a balanced (β, Δ) -graph if it is a bipartite graph with bandwidth at most β| W| and maximum degree at most Δ , and it also has a proper 2-coloring χ: W→ [2] such that | | χ- 1(1) | - | χ- 1(2) | | ≤ β| χ- 1(2) |. In this paper, we prove that for every γ> 0 and every natural number Δ , there exists a constant β> 0 such that for every balanced (β, Δ) -graph H on n vertices we have R(H,H,Cn)≤(3+γ)nfor all sufficiently large odd n. The upper bound is sharp for several classes of graphs. Let θn,t be the graph consisting of t internally disjoint paths of length n all sharing the same endpoints. As a corollary, for each fixed t≥ 1 , R(θn,t, θn,t, Cnt+λ) = (3 t+ o(1)) n, where λ= 0 if nt is odd and λ= 1 if nt is even. In particular, we have R(C2n, C2n, C2n+1) = (6 + o(1)) n, which is a special case of a result of Figaj and Łuczak (2018). © The Author(s), under exclusive licence to Springer Nature Japan KK, part of Springer Nature 2023.
Keyword:
Reprint 's Address:
Email:
Source :
Graphs and Combinatorics
ISSN: 0911-0119
Year: 2023
Issue: 3
Volume: 39
0 . 6
JCR@2023
0 . 6 0 0
JCR@2023
ESI HC Threshold:13
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: