TY - JOUR

T1 - Extremal problems and results related to Gallai-colorings

AU - Li, Xihe

AU - Broersma, Hajo

AU - Wang, Ligong

N1 - Funding Information:
Supported by the National Natural Science Foundation of China (No. 11871398 ) and China Scholarship Council (No. 201906290174 ).
Publisher Copyright:
© 2021 The Author(s)

PY - 2021/11

Y1 - 2021/11

N2 - A Gallai-coloring (Gallai-k-coloring) is an edge-coloring (with colors from {1,2,…,k}) of a complete graph without rainbow triangles. Given a graph H and a positive integer k, the k-colored Gallai-Ramsey number GRk(H) is the minimum integer n such that every Gallai-k-coloring of the complete graph Kn contains a monochromatic copy of H. In this paper, we consider two extremal problems related to Gallai-k-colorings. First, we determine upper and lower bounds for the maximum number of edges that are not contained in any rainbow triangle or monochromatic triangle in a k-edge-coloring of Kn. Second, for n≥GRk(K3), we determine upper and lower bounds for the minimum number of monochromatic triangles in a Gallai-k-coloring of Kn, yielding the exact value for k=3. Furthermore, we determine the Gallai-Ramsey number GRk(K4+e) for the graph on five vertices consisting of a K4 with a pendant edge.

AB - A Gallai-coloring (Gallai-k-coloring) is an edge-coloring (with colors from {1,2,…,k}) of a complete graph without rainbow triangles. Given a graph H and a positive integer k, the k-colored Gallai-Ramsey number GRk(H) is the minimum integer n such that every Gallai-k-coloring of the complete graph Kn contains a monochromatic copy of H. In this paper, we consider two extremal problems related to Gallai-k-colorings. First, we determine upper and lower bounds for the maximum number of edges that are not contained in any rainbow triangle or monochromatic triangle in a k-edge-coloring of Kn. Second, for n≥GRk(K3), we determine upper and lower bounds for the minimum number of monochromatic triangles in a Gallai-k-coloring of Kn, yielding the exact value for k=3. Furthermore, we determine the Gallai-Ramsey number GRk(K4+e) for the graph on five vertices consisting of a K4 with a pendant edge.

KW - Gallai-Ramsey theory

KW - Monochromatic copy of a graph

KW - Rainbow triangle

KW - Ramsey multiplicity

KW - Regularity lemma

KW - UT-Hybrid-D

UR - http://www.scopus.com/inward/record.url?scp=85111545436&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112567

DO - 10.1016/j.disc.2021.112567

M3 - Article

AN - SCOPUS:85111545436

VL - 344

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 11

M1 - 112567

ER -