Los números Ramsey para tres grafos y tres colores

• 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.

Palabras clave: Números Ramsey, coloración de grafos, números combinatorios, unión de grafos, sobreposición de grafos

Resumen

Dado un grafo $\Psi$ de orden $t$, simple, finito, y no vacío. Se llamará sobreposición de $\Psi$ al grafo completo $K_{t}$ definido por $\Psi\cup\overline{\Psi}$, donde $\overline{\Psi}$ denota el complemento de $\Psi$. Así, dados dos grafos $G$ y $H$, simples, conexos, finitos, no vacíos, y dos colores distintos. El número de Ramsey $R(G,H)$, se define como el menor entero positivo $t$, tal que existe algún grafo $\Psi$ que contiene una copia monocromática $G^{'}$ de $G$, o $\overline{\Psi}$ contiene una copia monocromática $H^{'}$ de $H$, y $K_{t}$ es una superposición de $\Psi$, es decir, $\Psi$ es un subgrafo de $K_{t}$. De forma similar, dados tres grafos $G$, $H_{1}$, y $H_{2}$, simples, conexos, finitos, no vacíos, y tres colores distintos $\{0,1,2\}$, se define como el número Ramsey $R(G,H_{1},H_{2})$ al menor entero positivo $t$ tal que existe una terna de grafos $(\Psi,\Psi_{1},\Psi_{2})$ que satisfagan lo siguiente: (1) $\overline{\Psi}=\Psi_{1}\cup\Psi_{2}$; (2) El grafo completo $K_{t}$ es la superposición de $\Psi$; (3) $|V(K_{t})|=|V(\Psi)|=|V(\Psi_{1})|=|V(\Psi_{2})|$; (4) $E(\Psi_{1})\cap E(\Psi_{2})=\emptyset$; y (5) El grafo $\Psi$ contiene una copia monocromática $G'$ de $G$, o de $\Psi_{1}$ puede extraerse una copia monocromática $H_{1}^{'}$ de $H_{1}$, o de $\Psi_{2}$ puede extraerse una copia monocromática $H_{2}^{'}$ de $H_{2}$. En este trabajo se muestra que, para $n\geq 4$, dados los grafos $K_{n}$ un grafo completo, $W_{n}$ un grafo rueda, y $D_{4}$ un grafo diamante. Si $t=\mbox{máx}\{|K_{n}|,|W_{n}|,|D_{4}|\}$, entonces $R(K_{n},W_{n},D_{4})=t+2$, para $t\in \mathbb{Z}^{+}\setminus\{1,2,3,4\}$.

Citas

[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.