Complete bipartite graphs without small rainbow stars

被引：2

作者：

Chen, Weizhen ^{[1
]}

Ji, Meng ^{[2
]}

Mao, Yaping ^{[3
]}

Wei, Meiqin ^{[4
]}

机构：

[1] Qinghai Normal Univ, Sch Math & Stat, Xining 810008, Qinghai, Peoples R China

[2] Tianjin Normal Univ, Coll Math Sci, Tianjin, Peoples R China

[3] Yokohama Natl Univ, Fac Environm & Informat Sci, 79-2 Tokiwadai,Hodogaya Ku, Yokohama 2408501, Japan

[4] Shanghai Maritime Univ, Coll Arts & Sci, Shanghai 201306, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2023年 / 340卷

基金：

美国国家科学基金会;

关键词：

Ramsey theory; Gallai-Ramsey number; Bipartite Gallai-Ramsey number; GALLAI-RAMSEY NUMBERS;

D O I：

10.1016/j.dam.2023.06.038

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The k-edge-colored bipartite Gallai-Ramsey number bgrk(G : H) is defined as the minimum integer n such that n2 > k and for every N > n, every edge-coloring (using all k colors) of complete bipartite graph KN,N contains a rainbow copy of G or a monochromatic copy of H. In this paper, we first study the structural theorem on the complete bipartite graph Kn,n with no rainbow copy of K1,3. Next, we utilize the results to prove the exact values of bgrk(P4 : H), bgrk(P5 : H), bgrk(K1,3 : H), where H is a various union of cycles and paths and stars. & COPY; 2023 Published by Elsevier B.V.

引用

页码：14 / 20

页数：7

共 28 条

[11] RAMSEY NUMBERS FOR LOCAL COLORINGS [J].

GYARFAS, A ;

LEHEL, J ;

SCHELP, RH ;

TUZA, ZS .

GRAPHS AND COMBINATORICS, 1987, 3 (03) :267-277

[12] Edge colorings of complete graphs without tricolored triangles [J].

Gyárfás, A ;

Simonyi, G .

JOURNAL OF GRAPH THEORY, 2004, 46 (03) :211-216

[13]

Gyarfas A., 1973, Periodica Mathematica Hungarica, V3, P299, DOI [10.1007/BF02018597, DOI 10.1007/BF02018597]

[14] Finding a monochromatic subgraph or a rainbow path [J].

Gyarfas, Andras ;

Lehel, Jeno ;

Schelp, Richard H. .

JOURNAL OF GRAPH THEORY, 2007, 54 (01) :1-12

[15] Ramsey-Type Results for Gallai Colorings [J].

Gyarfas, Andras ;

Sarkozy, Gabor N. ;

Sebo, Andras ;

Selkow, Stanley .

JOURNAL OF GRAPH THEORY, 2010, 64 (03) :233-243

[16] Improved Upper Bounds for Gallai-Ramsey Numbers of Paths and Cycles [J].

Hall, Martin ;

Magnant, Colton ;

Ozeki, Kenta ;

Tsugaki, Masao .

JOURNAL OF GRAPH THEORY, 2014, 75 (01) :59-74

[17]

Li X.H., 2022, THESIS NW POLYTECHNI

[18] The Erdos-Gyarfas function with respect to Gallai-colorings [J].

Li, Xihe ;

Broersma, Hajo ;

Wang, Ligong .

JOURNAL OF GRAPH THEORY, 2022, 101 (02) :242-264

[19] Monochromatic stars in rainbow K3-free and S3 +-free colorings [J].

Li, Xihe ;

Wang, Ligong .

DISCRETE MATHEMATICS, 2020, 343 (12)

[20] Forbidden rainbow subgraphs that force large monochromatic or multicolored k-connected subgraphs [J].

Li, Xihe ;

Wang, Ligong .

DISCRETE APPLIED MATHEMATICS, 2020, 285 :18-29

← 1 2 3 →