The Ramsey numbers for three graphs and three colors.

• José Figueroa Departamento de Quı́mica, Universidad Clodosbaldo Russián Cumaná, Venezuela.
• Tobı́as Rosas Soto Departamento de Matemática, Universidad del Zulia, Facultad Experimental de Ciencias, Maracaibo, Venezuela. https://orcid.org/0000-0002-8085-5011
• Henry Ramı́rez Departamento de Higiene y Seguridad Laboral Universidad Clodosbaldo Russián Cumaná, Venezuela.
• Armando Anselmi Departamento de Matemáticas, Universidad de Oriente, Cumaná, Venezuela.

Keywords: Ramsey numbers, graph coloring, combinatorial numbers, graph union, graph superposition

Abstract

Given a graph $\Psi$ of order $t$, simple, finite, and non-empty. An superposition of $\Psi$ will be called the complete graph $K_{t}$ defined by $\Psi\cup\overline{\Psi}$, where $\overline{\Psi}$ denotes the complement of $\Psi$. So, given two graphs $G$ and $H$, simple, connected, finite, non-empty, and two different colors. The Ramsey number $R(G, H)$, is defined as the smallest positive integer $t$ such that there exists some graph $\Psi$ that contains a monochrome copy $G'$ of $G$, or $\overline{\Psi}$ contains a monochrome copy $H'$ of $H$, and $K_{t}$ is a superposition of $\Psi$, that is, $\Psi$ is a subgraph of $K_{t}$. Similarly, given three graphs $G$, $H_{1}$, and $H_{2}$, simple, connected, finite non-empty, and three distinct colors $\{0,1,2\}$, is defined as the Ramsey number $R(G,H_{1},H_{2})$ to the smallest positive integer $t$ such that there exists a triplet of graphs $(\Psi,\Psi_{1},\Psi_{2})$ that satisfy the following: (1) $\overline{\Psi}=\Psi_{1}\cup\Psi_{2}$; (2) The complete graph $K_{t}$ is the superposition of $\Psi$; (3)$|V(K_{t})|=|V(\Psi)|=|V(\Psi_{1})|=|V(\Psi_{2})|$; (4) $E(\Psi_{1})\cap E(\Psi_{2})=\emptyset$; and (5) The graph $\Psi$ contains a monochrome copy $G'$ of $G$, or from $\Psi_{1}$ can be made a monochrome copy $H'_{1}$ of $H_{1}$, or from $\Psi_{2}$ a monochrome copy $H'_{2}$ of $H_{2}$ can be extracted. In this work it is shown that, for $n\geq 4$, given the graphs $K_{n}$ a complete graph, $W_{n}$ a roll graph, and $D_{4}$ a diamond graph. If $t=\mbox{m\'ax}\{|K_{n}|,|W_{n}|,|D_{4}|\}$, then $R(K_{n},W_{n},D_{4})=t+2$, for $t\in \mathbb{Z}^{+}\setminus\{1,2,3,4\}$.

References

[1] Baskoro E.T. (2002) “The Ramsey number of paths and small wheels”, J. Indones. Math. Soc. (MIHMI) (1), 13-16.
[2] Burr S.A. and Erdös P. (1984) “Generalizations of a Ramsey theoretic result of Chvatal”, Journal of Graph Theory 7: 39–51.
[3] Camacho D.J.A. Teorema del Índice de Poincaré, Universidad de Murcia 2012 − 2013.
[4] Chen Y.; Zhang Y.; and Zhang K. (2005) “The Ramsey number paths, versus wheels”, Descret Mathematics, 290, 85 − 87.
[5] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs, III:small off- diagonal numbers, Pacific Journal of Mathematics, 41 (1972), 335-345.
[6] P. Erdös, Some remarks on the theory of graphs Bull. Amer. Math. Soc. 53 (1947), 292-294.
[7] P. Erdös and G. Szekeres, On a combinatorial problem in geometry, Composition Mathematica 2 (1935), 463-470.
[8] J. Figueroa; F. Villarroel; H. Ramirez y J. Otero, Los Números de Ramsey con componente h−buena y secuencias simétricas, Divulgaciones Matemáticas, No 1 20(2019), 78-90.
[9] Radziszowski S.P. and Xia J. (1994) “Paths, cycles and wheels in graphs without antitriangles”, Australasion Journal of Combinatorics 9, 221-232.
[10] Surahmat and Baskoro E.T. (2001) “On the Ramsey Number of Path or Star versus W_4 or W_5 ”, Proc. Twelfth Autraslasian Workshop on Combinatorial Algorithms, Bandung, Indonesia, 14-17 July, 174-179.
[11] Villaroel F.; Figueroa J.; Marquez H. and Anselmi A. Un método algorı́tmico para el cálculo del número Baricéntrico de Ramsey para el grafo estrella Bol.soc. Paran. Mat. (3s) V.36. 2(2018), 169–183.
[12] Zhou H.L. (1995) “The Ramsey number of an odd cycles with respect to a wheel (in chinese”, Journal of Mathematics, Shuxu Zazhi (Wuhan), 15: 119–120.