On some three color Ramsey numbers for paths, cycles, stripes and stars (Q1741597)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On some three color Ramsey numbers for paths, cycles, stripes and stars |
scientific article |
Statements
On some three color Ramsey numbers for paths, cycles, stripes and stars (English)
0 references
3 May 2019
0 references
Let $G_{1}, \dots,G_{k}$ be finite simple undirected graphs. The multicolor Ramsey number $R(G_{1}, \dots,G_{k})$ is the smallest positive integer $n$ such that an arbitrary coloring of the edges of the complete graph on $n$ vertices with $k$ colors contains a monochromatic copy of $G_{i}$ in color $i$ for some $1 \le i \le k$. The bipartite Ramsey number is the smallest positive integer $b$ such that an arbitrary coloring of the edges of the complete bipartite graph $K_{b,b}$ with $k$ colors contains a monochromatic copy of bipartite $G_{i}$ in the $i$-th color for some $1 \le i \le k$. In this paper, the authors prove that for every finite simple undirected graph $H$ and bipartite graphs $G_{1}, \dots,G_{k}$ we have $R(H, G_{1}, \dots,G_{k}) \le R(H,K_{b,b})$, where $b$ is the bipartite Ramsey number corresponding to $G_{1}, \dots,G_{k}$. The paper contains some well-known and new upper estimations and explicit values of the multicoloring and bipartite Ramsey numbers corresponding to particular graphs such as paths, cycles, stripes or stars, which follows from the main result of the paper.
0 references
Ramsey number
0 references
bipartite Ramsey number
0 references
cycle
0 references
path
0 references
stripe
0 references
star
0 references