Gallai-Ramsey numbers for ℓ \ell -connected graphs Supported by the National Science Foundation of China (Nos. 12301458, 12401461, 12471329 and 12061059) and the Zhejiang Provincial Natural Science Foundation of China (No. LQ24A010005). The fourth-listed author is supported by a Scholarly Developmen

Zhao Wang, Lanyanni Zhang, Meiqin Wei, Mark Budden · 2026

Read Gallai-Ramsey numbers for ℓ \ell -connected graphs Supported by the National Science Foundation of China (Nos. 12301458, 12401461, 12471329 and 12061059) and the Zhejiang Provincial Natural Science Foundation of China (No. LQ24A010005). The fourth-listed author is supported by a Scholarly Developmen by Zhao Wang, Lanyanni Zhang, Meiqin Wei, Mark Budden (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13944.txt.

Introduction

Zhao Wang, Lanyanni Zhang, Meiqin Wei, and Mark Budden study Gallai-Ramsey numbers for linked graphs in 2026. A Gallai-Ramsey number is the smallest size that forces a pattern in colored graphs. Take a complete graph with edges colored in k colors, in an exact coloring. Past a set size, a target pattern from a family must appear.

The team focuses on l-connected graphs, which stay linked after small cuts. Ramsey theory shows order must emerge in large enough structures. These numbers mark the exact border where that order is forced. Such borders guide work in networks and combinatorics.

Catalog record

CREATORZhao Wang, Lanyanni Zhang, Meiqin Wei, Mark Budden
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-13944

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Gallai-Ramsey numbers for ℓ \ell -connected graphs Supported by the National Science Foundation of China (Nos. 12301458, 12401461, 12471329 and 12061059) and the Zhejiang Provincial Natural Science Foundation of China (No. LQ24A010005). The fourth-listed author is supported by a Scholarly Development Assignment Program grant from Western Carolina University. Zhao Wang, Lanyanni Zhang, Meiqin Wei, Mark Budden Abstract Given a nonempty graph G G , a collection of nonempty graphs ℋ \mathcal{H} , and a positive integer k k , the Gallai-Ramsey number gr k ​ ( G : ℋ ) \mathrm{gr}_{k}(G:\mathcal{H}) is defined to be the minimum positive integer n n such that every exact k k -edge-coloring of a complete graph K n K_{n} contains either a rainbow copy of G G or a monochromatic copy of some element in ℋ \mathcal{H} . In this paper, we obtain some exact values and general lower and upper bounds for gr k ​ ( G : ℱ ℓ ) \mathrm{gr}_{k}(G:\mathcal{F}^{\ell}) , where ℱ ℓ \mathcal{F}^{\ell} is the set of ℓ \ell -connected graphs and G ∈ { P 5 , K 1 , 3 } G\in\{P_{5},K_{1,3}\} . Keywords: Ramsey number; Gallai-Ramsey number; Rainbow path; ℓ \ell -connected graph. MSC 2020: 05C40; 05C55; 05D10. 1 Introduction The graphs considered in this paper are assumed to be nonempty, finite, and undirected simple graphs. We follow the notations and terminology introduced in the book [ 2 ] . If G is a graph, its vertex set is given by V(G) and its edge set is given by E(G) . We denote the order and size of G by |V(G)| and |E(G)| , respectively. For any n\in\mathbb{N} , define the notation [n]:=\{1,2,\dots,n\} . A k -edge-coloring of a graph G is a map \gamma:E(G)\longrightarrow[k] . Such a map is called exact if it is surjective. For a given k -edge-coloring \gamma of G , a subgraph of G is called monochromatic if all of its edges are in the same color class, and it is called rainbow if no two of its edges are in the same color class. If x\in V(G) , then we denote by d_{i}(x) the number of edges in color i that are incident with x , where i\in[k] . Let K_{n} , P_{n} , and C_{n} denote the complete graph, the path, and the cycle of order n , respectively. Let K_{1,n} be a star of size n and let nK_{2} be a matching of size n (i.e., the disjoint union of n copies of K_{2} ). If G is a graph and \emptyset\neq S\subset V(G) , then we denote by G-S the subgraph of G induced by V(G)\setminus S . When S=\{x\} , we write G-x in place of G-\{x\} . For any graphs G and H , the join of G and H , denoted G\vee H , is formed by taking the disjoint union of G and H , and adding in all of the edges between V(G) and V(H) . Given graphs H_{1},H_{2},\dots,H_{k} , the Ramsey number \mathrm{R}(H_{1},H_{2},...,H_{k}) is defined to be the least n\in\mathbb{N} such that every k -edge-coloring of K_{n} contains a monochromatic H_{i} in color i , for some i\in[k] . A k -edge-coloring of K_{\mathrm{R}(H_{1},H_{2},...,H_{k})-1} that avoids a copy of H_{i} in color i , for all i\in[k] , is called a critical coloring for \mathrm{R}(H_{1},H_{2},...,H_{k}) . If H_{1}=H_{2}=\cdot\cdot\cdot=H_{k}=H , then we simplify the notation for the Ramsey number to \mathrm{R}_{k}(H) . More generally, if \mathcal{H} is any nonempty set of graphs, then define the Ramsey number \mathrm{R}_{k}(\mathcal{H}) to be the minimum integer n\in\mathbb{N} such that every k -edge-coloring of K_{n} contains a monochromatic subgraph that is isomorphic to some graph in \mathcal{H} . A graph G is called \ell -connected if its order is greater than \ell and deleting fewer than \ell vertices results in a connected graph. Denote by \mathcal{F}^{\ell} the set of all \ell -connected graphs. In 1983, Matula [ 12 ] considered \mathrm{R}_{k}(\mathcal{F}^{\ell}) , proving the following theorem. Theorem 1.1 ( [ 12 ] ) . For k,\ell\geq 2 , we have 2k(\ell-1)+1\leq{\rm R}_{k}(\mathcal{F}^{\ell})<\frac{10}{3}k(\ell-1)+1. Furthermore, 4(\ell-1)+1\leq{\rm R}_{2}(\mathcal{F}^{\ell})<(3+\sqrt{11/3})(\ell-1)+1. In this paper, we consider the analogous problem for k -edge-colorings that avoid rainbow P_{5} -subgraphs or rainbow K_{1,3} -subgraphs. Definition 1 . Given a nonempty graph G , a collection of nonempty graphs \mathcal{H} , and k\in\mathbb{N} , the Gallai-Ramsey number \mathrm{gr}_{k}(G:\mathcal{H}) is defined to be the minimum integer n\in\mathbb{N} such that every exact k -edge-coloring of K_{n} contains either a rainbow copy of G or a monochromatic copy of some H\in\mathcal{H} . This variation of a Ramsey number is named after Tibor Gallai [ 4 ] who, in 1967, proved a result equivalent to a classification of rainbow K_{3} -free colorings of complete graphs. An English translation of [ 4 ] by Maffray and Priessmann can be found in [ 13 ] , and a statement of Gallai’s result in terms of rainbow K_{3} -free colorings can be found in [ 5 ] (see also [ 3 ] ). For additional details on Gallai-Ramsey numbers, we refer the reader to [ 7 , 8 , 9 , 10 , 11 , 16 , 17 ] . In order for K_{n} to have an exact k -edge-coloring, it is necessary that {n\choose 2}=\frac{n(n-1)}{2}\geq k, which is equivalent to n^{2}-n-2k\geq 0 . Solving this inequality for n , we find that {\rm gr}_{k}(G:\mathcal{H})\geq\left\lceil\frac{1+\sqrt{1+8k}}{2}\right\rceil, (1) for any graph G and any collection of graphs \mathcal{H} . The additional restriction of forbidding a rainbow copy of G renders it evident that {\rm gr}_{k}(G:\mathcal{H})\leq{\rm R}_{k}(\mathcal{H}) . Also, when k<|E(G)| , it is not possible to have a rainbow copy of G , and it follows that {\rm gr}_{k}(G:\mathcal{H})={\rm R}_{k}(\mathcal{H}) . As we will consider Gallai-Ramsey numbers of the forms {\rm gr}_{k}(P_{5}:\mathcal{F}^{\ell}) and {\rm gr}_{k}(K_{1,3}:\mathcal{F}^{\ell}) , we must first describe two structural theorems for the corresponding rainbow P_{5} -free and rainbow K_{1,3} -free colorings. Given an edge-colored complete graph, define V^{j} to be the set of vertices that are incident with at least one edge in color j , and denote by E^{j} the set of edges with color j . Thomason and Wagner [ 14 ] obtained the following structural theorem for edge-colored complete graphs that avoid a rainbow P_{5} . Theorem 1.2 ( [ 14 ] ) . Let n\geq 5 and consider an edge coloring of K_{n} that avoids a rainbow P_{5} . Then, up to isomorphism, and a possible reordering of the colors, one of the following holds: (a) At most three colors are used. (b) Color 1 is dominant; that is, the vertex set can be partitioned into A,V^{2},V^{3},V^{4},\ldots such that edges within V^{j} are colored 1 or j , edges meeting A and edges between V^{j} ( j\geq 2 ) are colored 1 . This implies that the sets V^{j} ( j\geq 2 ) are disjoint. (c) K_{n}-a is monochromatic for some vertex a . (d) There are three vertices a,b,c such that E^{2}=\{ab\} , E^{3}=\{ac\} , E^{4} contains bc plus perhaps some edges incident with a , and every other edge is in E^{1} . (e) There are four vertices a,b,c,d such that \{ab\}\subseteq E^{2}\subseteq\{ab,cd\} , E^{3}=\{ac,bd\} , E^{4}=\{ad,bc\} and every other edge is in E^{1} . (f)

Read the complete text