Gallai-Ramsey numbers for a class of graphs with five vertices

DOI10.1007/S00373-020-02194-5MaRDI QIDQ2657034zbMATH OpenOpenAlexFDO

Authors Xihe Li, Ligong Wang

Publication date 17 March 2021

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

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

zbMATH Keywords

Gallai-Ramsey numbermixed Ramsey spectrumrainbow triangle

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: Given two graphs $G$ and $H$, the $k$-colored Gallai-Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that every $k$-coloring of the complete graph on $n$ vertices contains either a rainbow copy of $G$ or a monochromatic copy of $H$. In this paper, we consider $g{r}_k(K_3:H)$ where $H$ is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai-Ramsey numbers for some of them have been studied step by step in several papers. We determine all the Gallai-Ramsey numbers for the remaining graphs, and we also obtain some related results for a class of unicyclic graphs.

Recommendations

• Gallai-Ramsey numbers for graphs with five vertices and chromatic number four
• Gallai-Ramsey numbers involving a rainbow 4-path
• Gallai-Ramsey numbers for graphs with chromatic number three
• Gallai-Ramsey numbers for rainbow paths
• Ramsey and Gallai-Ramsey numbers for two classes of unicyclic graphs

Cites work

• A conjecture on Gallai-Ramsey numbers of even cycles and paths
• A note on the monotonicity of mixed Ramsey numbers
• A translation of Gallai's paper: `Transitiv orientierbare Graphen'
• All partitions have small parts -- Gallai-Ramsey numbers of bipartite graphs
• Complete graphs and complete bipartite graphs without rainbow path
• Edge colorings of complete graphs without tricolored triangles
• Edge-colored complete graphs with precisely colored subgraphs
• Extensions of Gallai-Ramsey results
• Gallai-Ramsey numbers for books
• Gallai-Ramsey numbers for cycles
• Gallai-Ramsey numbers of odd cycles and complete bipartite graphs
• scientific article; zbMATH DE number 5717204 (Why is no real title available?)
• scientific article; zbMATH DE number 3458660 (Why is no real title available?)
• Improved upper bounds for Gallai-Ramsey numbers of paths and cycles
• On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph
• Rainbow generalizations of Ramsey theory: A survey
• Ramsey and Gallai-Ramsey numbers for stars with extra independent edges
• Ramsey numbers for graphs with five vertices
• Ramsey-type results for Gallai colorings
• Small Ramsey numbers
• Transitiv orientierbare Graphen

Cited in

(15)

• Ramsey and Gallai-Ramsey numbers for the union of paths and stars
• Gallai-Ramsey numbers for rainbow P₅ and monochromatic fans or wheels
• Gallai-Ramsey numbers for graphs with chromatic number three
• scientific article; zbMATH DE number 89408 (Why is no real title available?)
• Gallai-Ramsey numbers for graphs with five vertices and chromatic number four
• Gallai-Ramsey numbers involving a rainbow 4-path
• Gallai–Ramsey number for K5 ${K}_{5}$
• Gallai-Ramsey numbers for paths
• Ramsey and Gallai-Ramsey numbers for comb and sun graphs
• Ramsey and Gallai-Ramsey numbers for multiple triangles of graphs and their multiplicities
• Ordered Gallai-Ramsey numbers
• 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
• Complete graphs without proper subgraphs

This page was built for publication: Gallai-Ramsey numbers for a class of graphs with five vertices

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