On multicolor Ramsey number of paths versus cycles (Q625389)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On multicolor Ramsey number of paths versus cycles |
scientific article |
Statements
On multicolor Ramsey number of paths versus cycles (English)
0 references
17 February 2011
0 references
Let \(F_{1},F_{2},\dots ,F_{t}\) be graphs. The Ramsey number \( R(F_{1},F_{2},\dots ,F_{t})\) is defined as the smallest positive integer \(n\) such that if the edges of \(K_{n}\) are colored by \(t\) colors producing subgraphs \(H_{1},H_{2},\dots ,H_{t}\), then at least one \(H_{i}\) contains a subgraph isomorphic to \(F_{i}\). In this paper the authors determine the exact values of some three-color Ramsey numbers. Further, they improve the result of \textit{R. J. Faudree} and \textit{R. H. Schelp} [``Path Ramsey numbers in multicoloring'', J. Comb. Theory, Ser. B 19, 150--160 (1975; Zbl 0286.05111)] on the Ramsey number \(R(P_{n_{1}},P_{2n_{2}+\delta },\dots ,P_{2n_{t}})\). In fact, they prove the following result: Assume that \(\delta \in \{0,1\}\) and \(\Sigma \) denotes \(\sum_{i=1}^{t}(n_{i}-1)\). Then \(R(P_{2n_{1}+\delta },P_{2n_{2}},\dots ,P_{2n_{t}},P_{k}) = k+\Sigma \) where \(k\geq \Sigma ^{2}+2\Sigma +3\) if \(\delta =0\) and \(k\geq 2\Sigma ^{2}+5\Sigma +5\) otherwise. As a consequence of that, the authors obtain the following result: Let \(n_{1}\geq n_{1}\geq \dots \geq n_{1}\geq 2\) and \(m\) be positive integers and let \(\Sigma\) be as above. Then \(R(P_{2n_{1}},P_{2n_{2}}, \dots ,P_{2n_{t}})=k+\Sigma +1\) for \(2n_{1}\geq (\Sigma -n_{1}+2)^{2}+2\). Also, the authors conjecture that for positive integers \(n_{1}\geq n_{1}\geq \dots \geq n_{1}\geq 2,\) \(R(P_{2n_{1}},P_{2n_{2}},\dots ,P_{2n_{t}})=k+\sum_{i=1}^{t}(n_{i}-1)+1\).
0 references
Ramsey nubmer
0 references
paths
0 references
cycles
0 references