The multicolor star-critical Gallai-Ramsey number for a path of order 5

被引：0

作者：

Budden, Mark ^{[1
]}

机构：

[1] Western Carolina Univ, Dept Math & Comp Sci, Cullowhee, NC 28723 USA

来源：

DISCRETE MATHEMATICS LETTERS | 2023年 / 12卷

关键词：

Ramsey numbers; Gallai colorings; critical colorings; GRAPHS;

D O I：

10.47443/dml.2023.115

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, the t-color star-critical Gallai-Ramsey number for a path of order 5 is determined. It is proved that t+1 edges are both necessary and sufficient to add between a vertex and a critical coloring for the t-color Gallai-Ramsey number for P-5 in order to guarantee the existence of a monochromatic subgraph isomorphic to P-5. The proof depends on a well-known structural result for Gallai colorings as well as a general lower bound due to Faudree, Gould, Jacobson, and Magnant.

引用

页码：145 / 149

页数：5

共 10 条

[1]

Budden M., 2023, Star-critical Ramsey numbers for graphs

[2]

Faudree RJ, 2010, AUSTRALAS J COMB, V46, P269

[3]

Fujita S., 2014, THEORY APPL GRAPHS

[4] TRANSITIV ORIENTIERBARE GRAPHEN [J].

GALLAI, T .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1967, 18 (1-2) :25-&

[5]

Gerencser L., 1967, ANN U SCI BUDAP, V10, P167, DOI DOI 10.1007/BF01350150

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

Gyárfás, A ;

Simonyi, G .

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

[7]

Hook J., 2010, The classification of critical graphs and star-critical Ramsey numbers

[8] CRITICAL GRAPHS FOR R(Pn, Pm) AND THE STAR-CRITICAL RAMSEY NUMBER FOR PATHS [J].

Hook, Jonelle .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2015, 35 (04) :689-701

[9]

Magnant C., 2020, TOPICS GALLAI RAMSEY, DOI [10.1007/978-3-030-48897-0, DOI 10.1007/978-3-030-48897-0]

[10] Star-Critical Gallai-Ramsey Numbers of Graphs [J].

Su, Xueli ;

Liu, Yan .

GRAPHS AND COMBINATORICS, 2022, 38 (05)

← 1 →