Weakened Gallai–Ramsey number for various graphs of order up to six

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.