Ramsey and Gallai-Ramsey number for wheels

DOI10.1007/S00373-021-02406-6zbMATH Open1485.05110arXiv1905.12414OpenAlexW4210737048MaRDI QIDQ2115156FDOQ2115156

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

Publication date: 15 March 2022

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

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.

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

Recommendations

• A note on Gallai-Ramsey number of even wheels
• Gallai-Ramsey numbers for rainbow \(P_5\) 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

zbMATH Keywords

wheel2-color Ramsey numbergeneral \(k\)-colored Gallai-Ramsey number

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• On the sum number of wheels
• Complete bipartite graphs without small rainbow subgraphs
• Gallai-Ramsey number of an 8-cycle
• Gallai-Ramsey numbers involving a rainbow 4-path
• Gallai-Ramsey numbers for books
• A note on Gallai-Ramsey number of even wheels
• Weakened Gallai-Ramsey numbers
• Gallai-Ramsey numbers for graphs with five vertices and chromatic number four
• Gallai-Ramsey numbers for rainbow \(P_5\) and monochromatic fans or wheels
• Gallai-Ramsey numbers for paths
• Ramsey and Gallai-Ramsey numbers for comb and sun graphs
• Size Gallai-Ramsey number

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)