Weakened Gallai–Ramsey number for various graphs of order up to six
No Thumbnail Available
Date
2026
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Gallai–Ramsey theory examines how edge colorings of complete graphs avoiding rain
bow triangles inevitably yield monochromatic subgraphs. In this work, we generalize
this framework by introducing the weakened Gallai–Ramsey number grs
t(G), defined as
the smallest integer p such that every Gallai t-coloring of Kp
contains a copy of G using
at most s<t colors. We determine exact values and bounds for grs
t(G) for several graph
classes, including complete graphs, books, wheels, and complete bipartite graphs. These
results extend classical Gallai–Ramsey theory and provide new insight into the behavior
of multicolored subgraphs under constrained colorings.
© 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI
training, and similar technologies.