Indexed by:
Abstract:
A graph H = (W, E-H) is said to have bandwidth at most b if there exists a labeling of W as w(1), w(2),..., w(n) such that vertical bar i - j vertical bar <= b for every edge w(i)w(j) is an element of E-H. We say that H is a balanced (beta, Delta)-graph if it is a bipartite graph with bandwidth at most beta vertical bar W vertical bar and maximum degree at most Delta, and it also has a proper 2-coloring chi : W -> [2] such that parallel to chi(-1)(1)vertical bar - vertical bar chi(-1)(2)parallel to <= beta vertical bar chi(-1)(2)|. In this paper, we prove that for every gamma > 0 and every natural number Delta, there exists a constant beta > 0 such that for every balanced (beta, Delta)-graph H on n vertices we have R(H, H, C-n) <= (3 + gamma)n for all sufficiently large odd n. The upper bound is sharp for several classes of graphs. Let theta(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(theta(n,t), theta(n,t), Cnt+lambda) = (3t + o(1))n, where lambda = 0 if nt is odd and lambda = 1 if nt is even. In particular, we have R(C-2n, C-2n, C2n+1) = (6 + o(1))n, which is a special case of a result of Figaj and Luczak (2018).
Keyword:
Reprint 's Address:
Email:
Version:
Source :
GRAPHS AND COMBINATORICS
ISSN: 0911-0119
Year: 2023
Issue: 3
Volume: 39
0 . 6
JCR@2023
0 . 6 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
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: