Ramsey and Gallai-Ramsey number for wheels

DOI10.1007/S00373-021-02406-6MaRDI QIDQ2115156zbMATH OpenOpenAlexFDO

Authors Yaping Mao, Zhao Wang, Colton Magnant, Ingo Schiermeyer

Publication date 15 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.12414

zbMATH Keywords

2-color Ramsey numbergeneral \(k\)-colored Gallai-Ramsey numberwheel

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given a graph $G$ and a positive integer $k$, define the emph{Gallai-Ramsey number} to be the minimum number of vertices $n$ such that any $k$-edge coloring of $K_n$ contains either a rainbow (all different colored) triangle or a monochromatic copy of $G$. Much like graph Ramsey numbers, Gallai-Ramsey numbers have gained a reputation as being very difficult to compute in general. As yet, still only precious few sharp results are known. In this paper, we obtain bounds on the Gallai-Ramsey number for wheels and the exact value for the wheel on $5$ vertices.

Review text

Given two graphs \(G\) and \(H\), the general \(k\)-colored Gallai-Ramsey number gr\(_{k}(G:H)\) is defined to be the minimum integer \(m\) such that every \(k\)-coloring of the complete graph on \(m\) vertices contains either a rainbow copy of \(G\) or a monochromatic copy of \(H\). In this paper, the authors give upper and lower bounds for classical Ramsey number of the wheel \(W_n\) as follows: For \(k \geq 1\) and \(n \geq 7\), \(3n-3 \leq R(W_n,W_n) \leq 8n - 10\), if \(n\) is even and \(2n - 2 \leq R(W_n,W_n)\leq 6n - 8\), if \(n\) is odd. They also obtain the exact value of gr\(_{k}(K_3:W_5)\) for every \(k\geq 1\). Finally, general upper and lower bounds on the Gallai-Ramsey numbers for all wheels are provided.

Recommendations

• A note on Gallai-Ramsey number of even wheels
• Gallai-Ramsey numbers for rainbow P₅ and monochromatic fans or wheels
• Gallai-Ramsey numbers of odd cycles and complete bipartite graphs
• Gallai-Ramsey numbers for books
• Gallai-Ramsey numbers involving a rainbow 4-path

Cites work

• All Ramsey numbers for cycles in graphs
• Edge colorings of complete graphs without tricolored triangles
• Extending cycles in graphs
• Generalized and geometric Ramsey numbers for cycles.
• Lambda composition
• On a Ramsey-type problem of J. A. Bondy and P. Erdős. II
• Rainbow generalizations of Ramsey theory: A survey
• Ramsey and Gallai-Ramsey numbers for stars with extra independent edges
• The Ramsey numbers for cycles versus wheels of odd order
• Transitiv orientierbare Graphen

Cited in

(16)

• Gallai-Ramsey numbers for rainbow P₅ and monochromatic fans or wheels
• Gallai-Ramsey numbers for books
• A note on Gallai-Ramsey number of even wheels
• Weakened Gallai-Ramsey numbers
• Gallai-Ramsey number of an 8-cycle
• Gallai-Ramsey numbers for graphs with five vertices and chromatic number four
• On the sum number of wheels
• Gallai-Ramsey numbers involving a rainbow 4-path
• Size Gallai-Ramsey number
• Complete bipartite graphs without small rainbow subgraphs
• Gallai-Ramsey numbers for paths
• Ramsey and Gallai-Ramsey numbers for comb and sun graphs
• Ramsey and Gallai-Ramsey numbers for forests
• Gallai-Ramsey numbers for three graphs on at most five vertices
• Ramsey and Gallai-Ramsey numbers of cycles and books
• Disproofs of four conjectures on Gallai-Ramsey numbers

This page was built for publication: Ramsey and Gallai-Ramsey number for wheels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115156)