TY - JOUR
T1 - Complete graphs and complete bipartite graphs without rainbow path
AU - Li, Xihe
AU - Wang, Ligong
AU - Liu, Xiangxiang
N1 - Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2019/7
Y1 - 2019/7
N2 - Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs G and H, the k-colored Gallai–Ramsey number gr k (G:H) is defined to be the minimum integer n such that [Formula Presented] and for every N≥n, every rainbow G-free coloring (using all k colors) of the complete graph K N contains a monochromatic copy of H. In this paper, we first provide some exact values and bounds of gr k (P 5 :K t ). Moreover, we define the k-colored bipartite Gallai–Ramsey number bgr k (G:H) as the minimum integer n such that n 2 ≥k and for every N≥n, every rainbow G-free coloring (using all k colors) of the complete bipartite graph K N,N contains a monochromatic copy of H. Furthermore, we describe the structures of complete bipartite graph K n,n with no rainbow P 4 and P 5 , respectively. Finally, we find the exact values of bgr k (P 4 :K s,t ) (1≤s≤t), bgr k (P 4 :F) (where F is a subgraph of K s,t ), bgr k (P 5 :K 1,t ) and bgr k (P 5 :K 2,t ) by using the structural results.
AB - Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs G and H, the k-colored Gallai–Ramsey number gr k (G:H) is defined to be the minimum integer n such that [Formula Presented] and for every N≥n, every rainbow G-free coloring (using all k colors) of the complete graph K N contains a monochromatic copy of H. In this paper, we first provide some exact values and bounds of gr k (P 5 :K t ). Moreover, we define the k-colored bipartite Gallai–Ramsey number bgr k (G:H) as the minimum integer n such that n 2 ≥k and for every N≥n, every rainbow G-free coloring (using all k colors) of the complete bipartite graph K N,N contains a monochromatic copy of H. Furthermore, we describe the structures of complete bipartite graph K n,n with no rainbow P 4 and P 5 , respectively. Finally, we find the exact values of bgr k (P 4 :K s,t ) (1≤s≤t), bgr k (P 4 :F) (where F is a subgraph of K s,t ), bgr k (P 5 :K 1,t ) and bgr k (P 5 :K 2,t ) by using the structural results.
KW - Bipartite Gallai–Ramsey number
KW - Gallai–Ramsey number
KW - Rainbow path
UR - http://www.scopus.com/inward/record.url?scp=85065209965&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2019.04.010
DO - 10.1016/j.disc.2019.04.010
M3 - 文章
AN - SCOPUS:85065209965
SN - 0012-365X
VL - 342
SP - 2116
EP - 2126
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 7
ER -