Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

https://produccioncientificaluz.org/index.php/divulgaciones/

DOI: https://doi.org/10.5281/zenodo.11516259

(CC BY-NC-SA 4.0)

Autor(es)

e-ISSN 2731-2437

p-ISSN 1315-2068

Los n´umeros Ramsey para tres grafos y tres

colores

The Ramsey numbers for three graphs and three colors.

Jos´e Figueroa (jose3765@gmail.com)

Departamento de Qu´ımica

Universidad Clodosbaldo Russi´an

Cuman´a, Venezuela.

Tob´ıas Rosas Soto (tjrosas@gmail.com)

ORCID: https://orcid.org/0000-0002-8085-5011

Departamento de Matem´atica

Universidad del Zulia, Facultad Experimental de Ciencias

Maracaibo, Venezuela.

Henry Ram´ırez (hlramirez6@hotmail.com)

Departamento de Higiene y Seguridad Laboral

Universidad Clodosbaldo Russi´an

Cuman´a, Venezuela.

Armando Anselmi (alanselm2010@gmail.com)

Departamento de Matem´aticas

Universidad de Oriente

Cuman´a, Venezuela.

Resumen

Dado un grafo Ψ de orden t, simple, ﬁnito, y no vac´ıo. Se llamar´a sobreposici´on de Ψ al

grafo completo Ktdeﬁnido por Ψ ∪Ψ, donde Ψ denota el complemento de Ψ. As´ı, dados

dos grafos GyH, simples, conexos, ﬁnitos, no vac´ıos, y dos colores distintos. El n´umero de

Ramsey R(G, H), se deﬁne como el menor entero positivo t, tal que existe alg´un grafo Ψ

que contiene una copia monocrom´atica G

0de G, o Ψ contiene una copia monocrom´atica H

de H, y Ktes una superposici´on de Ψ, es decir, Ψ es un subgrafo de Kt. De forma similar,

dados tres grafos G,H1, y H2, simples, conexos, ﬁnitos, no vac´ıos, y tres colores distintos

{0,1,2}, se deﬁne como el n´umero Ramsey R(G, H1, H2) al menor entero positivo ttal que

existe una terna de grafos (Ψ,Ψ1,Ψ2) que satisfagan lo siguiente: (1) Ψ = Ψ1∪Ψ2; (2) El

grafo completo Ktes la superposici´on de Ψ; (3) |V(Kt)|=|V(Ψ)|=|V(Ψ1)|=|V(Ψ2)|; (4)

E(Ψ1)∩E(Ψ2) = ∅; y (5) El grafo Ψ contiene una copia monocrom´atica G0de G,odeΨ1

puede extraerse una copia monocrom´atica H

1de H1, o de Ψ2puede extraerse una copia mo-

nocrom´atica H

2de H2. En este trabajo se muestra que, para n≥4, dados los grafos Knun

grafo completo, Wnun grafo rueda, y D4un grafo diamante. Si t= m´ax{|Kn|,|Wn|,|D4|},

entonces R(Kn, Wn, D4) = t+ 2, para t∈Z+\ {1,2,3,4}.

Recibido 03/05/2022. Revisado 21/06/2022. Aceptado 13/10/2022.

MSC (2010): Primary 05C55; Secondary 05C15.

Autor de correspondencia: Jos´e Figueroa

Los n´umeros Ramsey para tres grafos y tres colores 13

Palabras y frases clave: N´umeros Ramsey, coloraci´on de grafos, n´umeros combinato-

rios, uni´on de grafos, sobreposici´on de grafos.

Abstract

Given a graph Ψ of order t, simple, ﬁnite, and non-empty. An superposition of Ψ will

be called the complete graph Ktdeﬁned by Ψ ∪Ψ, where Ψ denotes the complement of

Ψ. So, given two graphs Gand H, simple, connected, ﬁnite, non-empty, and two diﬀer-

ent colors. The Ramsey number R(G, H), is deﬁned as the smallest positive integer tsuch

that there exists some graph Ψ that contains a monochrome copy G0of G, or Ψ contains

a monochrome copy H0of H, and Ktis a superposition of Ψ, that is, Ψ is a subgraph

of Kt. Similarly, given three graphs G,H1, and H2, simple, connected, ﬁnite non-empty,

and three distinct colors {0,1,2}, is deﬁned as the Ramsey number R(G, H1, H2) to the

smallest positive integer tsuch that there exists a triplet of graphs (Ψ,Ψ1,Ψ2) that satisfy

the following: (1) Ψ = Ψ1∪Ψ2; (2) The complete graph Ktis the superposition of Ψ;

(3)|V(Kt)|=|V(Ψ)|=|V(Ψ1)|=|V(Ψ2)|; (4) E(Ψ1)∩E(Ψ2) = ∅; and (5) The graph Ψ

contains a monochrome copy G0of G, or from Ψ1can be made a monochrome copy H0

1of

H1, or from Ψ2a monochrome copy H0

2of H2can be extracted. In this work it is shown

that, for n≥4, given the graphs Kna complete graph, Wna roll graph, and D4a diamond

graph. If t= m´ax{|Kn|,|Wn|,|D4|}, then R(Kn, Wn, D4) = t+ 2, for t∈Z+\ {1,2,3,4}.

Key words and phrases: Ramsey numbers, graph coloring, combinatorial numbers,

graph union, graph superposition.

1 Introducci´on

El origen de la teor´ıa de grafos se remonta al siglo XVIII, en el a˜no 1736, con el problema de los

puentes de K¨onigsberg, el cual consist´ıa en encontrar un camino que recorriera los siete puentes

del r´ıo Pregel. La soluci´on a dicho planteamiento fue considerada como el primer resultado de la

teor´ıa de grafos y el primer resultado topol´ogico en la geometr´ıa. Se deﬁne el grafo Gcomo un

par de conjuntos (V, E), denotado por G= (V, E), donde Ves un conjunto no vac´ıo de elementos

llamados v´ertices o nodos y Ees un conjunto de pares no ordenados de elementos de V, llamados

lados o aristas; si Gno posee lazos ni lados m´ultiples es un grafo simple. El orden de G, denotado

por |V|, es el n´umero de v´ertices de G. En 1933, Erd¨os y Szekeres en [7], inician el estudio de la

teor´ıa Ramsey, llamada as´ı en honor a Frank P. Ramsey. Tiempo despu´es descubrieron la conexi´on

con los trabajos que Ramsey consigui´o en su corta vida. En 1947, P. Erd¨os en [6], aﬁrma que el

propio Ramsey hab´ıa observado que

R(k, k)≤2

k(k−1)

2,(1.1)

que luego mejor´o obteniendo:

R(k, k)≤k!,(1.2)

aunque ´el mismo aventuraba que esta cota podr´ıa reducirse. En 1972, Chv´atal y Harary en [5],

dan en forma general una cota inferior para los n´umeros Ramsey:

R(G, H)≥(c(G)−1)(χ(H)−1) + 1,(1.3)

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

14 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

donde c(G) es el orden de la componente m´as larga de G, y χ(H) es el n´umero crom´atico del

grafo H. En 1984, Burr y P. Erd¨os en [2], dan una cota inferior m´as general que la de Chv´atal y

Harary:

R(G, H)≥(n−1)(χ(H)−1) + σ(H),(1.4)

donde Ges un grafo conexo de orden nyσ(H) el excedente crom´atico del grafo H. El grafo Ges

bueno con respecto a H, denotado por H-bueno, si es validad la desigualdad (1.4) de lo contrario

Gno contendr´ıa componentes H-buena. En 1994, Radziszowski y Xia en [9], dieron un m´etodo

sencillo y uniﬁcado para mostrar resultados del n´umero de Ramsey R(C3, G), donde Ges un

camino, ciclo o una rueda. En 1995, Zhou en [12], prueba que R(Cn, Wm)=2m+ 1, para n≥3

impar y m≥5n−7. En 2001, Surahmat y Baskoro demostraron en [10] que, para cada n≥3, se

tiene que R(Pn, W4)=2n−1 y R(Pn, W5) = 3n−2. En 2002, Baskoro et al [1], y en 2005, Chen

et al en [4], probaron que R(Pn, W6)=2n−1, para todo n≥6 y R(Pn, W7)=3n−2, para todo

n≥7, respectivamente. En 2018, Villaroel et al en [11], estudiaron un m´etodo algor´ıtmico para

el c´alculo del n´umero baric´entrico de Ramsey para el grafo estrella. En 2019, Figueroa et al [8],

estudiaron los n´umeros de Ramsey con componente h-buena y secuencias sim´etricas.

Dado un grafo Ψ de orden t, simple, ﬁnito, y no vac´ıo. Se llamar´a sobreposici´on de Ψ al grafo

completo Ktdeﬁnido por Ψ ∪Ψ, donde Ψ denota el complemento de Ψ. El n´umero de Ramsey

R(G, H), se deﬁne como el menor entero positivo t, tal que existe alg´un grafo Ψ de orden t, que

contiene una copia monocrom´atica G0de G, o Ψ contiene una copia monocrom´atica H0de Hy

Ktes una superposici´on de Ψ. N´otese que en esta deﬁnici´on de n´umero Ramsey se utilizan dos

grafos y dos colores. El objetivo de este trabajo es determinar un m´etodo, que permita hallar el

menor grafo completo KR(Kn,Wn,D4)= Ψ ∪Ψ1∪Ψ2, con Ψ = Ψ1∪Ψ2, que coloreado con tres

colores diferentes, cumpla una de las siguientes aﬁrmaciones:

•Ψ contiene una copia monocrom´atica G0de Kn.

•Ψ1contenga una copia monocrom´atica H0

1de Wn.

•Ψ2contenga una copia monocrom´atica H0

2de D4.

En el ejemplo que se presentar´a nes el orden inicial del grafo dado, y t= m´ax{|kn|,|Wn|,|D4|}.

El procedimiento fundamental es: primero incrementar el n´umero de v´ertices ten una unidad

(t→t+ 1) formando el grafo completo Kt+1. Luego, si

|E(Kt+1)|<|E(Kn)|+|E(Wn)|+|E(D4)|,

en cuyo caso

|E(Ψ)|<|E(Kn)|,|E(Ψ1)|<|E(Wn)|,y|E(Ψ2)|<|E(D4)|.

Se incrementa nuevamente el n´umero de v´ertices de t+ 1 a t+ 2, formando el grafo completo

Kt+2 y obteniendo que

|E(Ψ)|≥|E(Kn)|,´o |E(Ψ1)|≥|E(Wn)|´o |E(Ψ2)| ≥ |E(D4)|.

Para el c´alculo del n´umero de aritas del grafo Kt+2 se utiliza el polinomio P(t) = t2−t

2que

proviene del n´umero combinatorio t

2que representa el n´umero de aristas del grafo Kt. Con

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

Los n´umeros Ramsey para tres grafos y tres colores 15

dicho polinomio se deﬁnen |E(Kt+2)|=P(t+ 2). Para determinar el n´umero de secuencias si

con las que se colorea el grafo Kt+2 se deﬁne el polinomio Q(t) = P(t+ 2)

2, todo esto para

t≥5. Con esto se deﬁne una aplicaci´on Υ : E(Kt+2)→(si)Q(t)

i=1 , que colorea los lados de

Kt+2 = Ψ ∪Ψ1∪Ψ2, con cada si, para cada t≥5, tal que satisfacen las deﬁniciones 2.1 y

2.2 de la Secci´on 2 de este manuscrito, es decir, garantiza la existencia de una funci´on biyectiva

ϕque preserva las adyacencias entre grafos. Dicho con otras palabras, Ψ contiene una copia

monocrom´atica G0de Kn,oΨ1contiene una copia H0

1de Wn,oΨ2contiene una copia H0

2de

D4. En la Secci´on 2 se dan algunas deﬁniciones y enunciados que sustent´an este trabajo, en la

Secci´on 3 se da un ejemplo y un cuadro de valores de donde se ilustra el resultado y ﬁnalmente

en la Secci´on 4 se da el resultado y se demuestra.

2 Preliminares

Deﬁnici´on 2.1. Sean GyHdos grafos distintos del vac´ıo y se consideran dos colores diferentes.

Se dice que el par (G, H) es isomorfo al par (G0, H0), si Ges bueno con respecto a H, si existe

un grafo Ψ tal que G0

CΨ o H0

CΨ. Adem´as, satisfacen la existencia de una funci´on biyectiva

ϕque preserva las adyacencias entre los v´ertices de los grafos, es decir,

i) ϕ:V(G0)→V(G); uivj∈E(G0)⇔ϕ(ui)ϕ(vj)∈E(G) o

ii) ϕ:V(H0)→V(H); ukvp∈E(H0)⇔ϕ(uk)ϕ(vp)∈E(H)

Deﬁnici´on 2.2. Sea Ψ un grafo de orden t, simple, ﬁnito, y no vac´ıo. Se llamar´a sobreposici´on

de Ψ al grafo completo Ktdeﬁnido por Ψ ∪Ψ, donde Ψ denota el complemento de Ψ.

Proposici´on 2.1. Dado el grafo completo Kt, con t∈N, se tiene que

|E(Kt)|=Ct

2= t

2!=t(t−1)

Deﬁnici´on 2.3. Dado el grafo completo Kt, con t∈N, se deﬁnir´a

P(t) = |E(Kt)|=t(t−1)

al polinomio que determina el n´umero de aristas del grafo completo Kt.

Corolario 2.1. Dados los grafos completos Kt+1 yKt+2, con t∈N, se tiene que:

P(t+ 1) = (t+ 1)(t)

2=t2+t

2yP(t+ 2) = (t+ 2)(t+ 1)

2=t2+ 3t+ 2

Deﬁnici´on 2.4. Sean {0,1,2}tres colores dados y s= (x1, . . . , xr) la sucesi´on, con xi∈ {0,1,2},

construida de la siguiente forma:

1. La sucesi´on ses monocrom´atica. Fijado x1, se tiene que xi=xi−1para i= 2, . . . , r.

2. La sucesi´on ses bicrom´atica. Hay un ´ındice k, con 1 ≤k≤r, tal que xk−1< xky

x1=· · · =xk−1yxk=· · · =xr

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

16 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

3. La sucesi´on ses tricrom´atica. Hay dos ´ındices kyq, con k, q ≤ryk < q, tales que

xk< xq< xry

x1=· · · =xkxk+1 =· · · =xqxq+1 =· · · =xr

Proposici´on 2.2. Sean {0,1,2}tres colores dados y rla longitud de la sucesi´on s= (x1, . . . , xr)

construida como en la Deﬁnici´on 2.4, entonces el n´umero de suceciones posibles formadas por los

tres colores est´a dado por el n´umero combinatorio

r+ 2

2=(r+ 2)(r+ 1)

Demostraci´on. Claramente se tiene una sola secuencia stal que xi= 0 para todo i= 1, . . . , r.

Ahora se proceder´a a ﬁjar el mayor n´umero de entradas de scon el color 0 y se determinar´a la

cantidad de sucesiones que se puedan formar con los colores {0,1,2}. Si xi= 0 para i= 1, . . . , r−1

se obtienen 2 sucesiones ya que xr= 1 o xr= 2. Si se hace xi= 0 para i= 1, . . . , r −2 se obtienen

3 sucesiones ya que las ´ultimas dos coordenas podr´ıan ser (1,1), o (1,2) o (2,2). N´otese que bastan

tres cambios para llegar de (1,1) hasta (2,2), es decir, el n´umero de coordenadas no ﬁjadas m´as

una unidad.

Razonando de forma similar se tendr´ıa que para r−kcoordenadas ﬁjadas, y por tanto kno

ﬁjadas el n´umero se sucesiones tricrom´aticas que se pueden obtener son k+ 1. Teniendo as´ı el

siguiente cuadro

Coord. Fijas r r −1r−2· · · r−k· · · 3 2 1

Coord. No Fijas 01 2· · · k· · · r−3r−2r−1

# Sucesiones 12 3· · · k+ 1 · · · r−2r−1r

De manera que se tiene, ﬁjando el color 0, un total de

r−1

i=0

(i+ 1) =

i=1

i=r(r+ 1)

Por ´ultimo, n´otese que faltan la sucesiones stal que xi= 1 para todo i= 1, . . . , r y la sucesiones

bicrom´aticas con los colores 1 y 2, las cuales suman r+ 1, pues es rel n´umero de cambios que se

deben realizar para llegar de

(1,...,1

| {z }

r−veces

)−→

hasta (2,...,2

| {z }

r−veces

)

Por tanto, se tiene un total de

r(r+ 1)

2+r+ 1 = (r+ 1) r

2+ 1=(r+ 2)(r+ 1)

2=(r+ 2)(r+ 1)r!

2!r!=r+ 2

2

Corolario 2.2. Sean el grafo completo Kt+2, con t∈N, y {0,1,2}tres colores. Entonces el

n´umero de sucesiones s, deﬁnidas como en la Proposici´on 2.2, para colorear los lados de Kt+2

est´a dada por el n´umero

Q(t) = P(t+ 2) + 2

2.

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

Los n´umeros Ramsey para tres grafos y tres colores 17

Demostraci´on. Basta hacer r=P(t+ 2) y, aplicando el Corolario 2.1 y la Proposici´on 2.2, se

obtiene el resultado deseado.

Deﬁnici´on 2.5. Sean G,H1yH2tres grafos, simples, conexos, ﬁnitos, no vac´ıos y {0,1,2}tres

colores diferentes. El n´umero de Ramsey denotado por R(G, H1, H2), es el menor entero positivo

t, tal que existe una terna de grafos (Ψ,Ψ1,Ψ2) que satisface:

1. Ψ = Ψ1∪Ψ2.

2. El grafo completo Ktes la superposici´on de Ψ.

3. |V(Kt)|=|V(Ψ)|=|V(Ψ1)|=|V(Ψ2)|.

4. E(Ψ1)∩E(Ψ2) = ∅.

5. El grafo Ψ contiene una copia monocrom´atica G0de Go de Ψ1puede extraerse una copia

monocrom´atica H0

1de H1o de Ψ2puede extraerse una copia monocrom´atica H0

2de H2.

Deﬁnici´on 2.6. Sean G,H1yH2tres grafos distintos de vac´ıos. Se dice que la tr´ıada (G, H1, H2)

es isomorfa a la tr´ıada (G0, H0

1, H0

2), si Ges bueno con respecto a H1,oaH2, es decir, existe una

tr´ıada (Ψ,Ψ1,Ψ2) tal que

CΨ, H

1CΨ1,yH

2CΨ2.

Adem´as, existe una funci´on biyectiva ϕque preserva las adyacencias entre los v´ertices de los

grafos, es decir,

i) ϕ:V(G0)→V(G); uivj∈E(G0)⇔ϕ(ua)ϕ(vb) = waxb∈E(G) o

ii) ϕ:V(H0

1)→V(H1); ucvd∈E(H0

1)⇔ϕ(uc)ϕ(vd) = yczd∈E(H1) o

iii) ϕ:V(H0

2)→V(H2); uevf∈E(H0

2)⇔ϕ(ue)ϕ(vf) = yezf∈E(H2).

Deﬁnici´on 2.7. Sean G,H1yH2tres grafos simples, conexos, ﬁnitos y no vac´ıos. Sean

P(t+ 2) = t+ 2

2yQ(t) = P(t+ 2)

2.

Se dice que KR(G,H1,H2), contiene componentes h-buena, si al colorear los lados de

KR(G,H1,H2)= Ψ ∪Ψ1∪Ψ2

con cada secuencia si, deﬁnidas como en la Deﬁnici´on 2.4 para todo i= 1,· · · , Q(t), donde

|E(KR(G,H1,H2))|=P(t+ 2) es el tama˜no de cada secuencia para t≥5, existe una coloraci´on

con sidonde Ψ contiene una copia monocrom´atica G0de Gcon el primer color, o de Ψ1puede

extraerse una copia monocrom´atica H0

1de H1con el segundo color, o de Ψ2puede extraerse una

copia monocrom´atica H0

2de H2con el tercer color.

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

18 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

3 Ejemplo ilustrativo

Ejemplo 3.1. Sea n= 4 y t´omense los grafos G=K4el completo, H1=W4la rueda, y

H2=K4−lel diamante. Consid´erese t=m´ax{|G|,|H1|,|H2|} =m´ax{4,5,4}= 5. Luego, se

aumenta el valor de ten una unidad (t→t+ 1), para formar el grafo completo K6. Usando el

Corolario 2.1 se tiene que el n´umero de lados

|E(K6)|=P(5 + 1) = 52+ 5

2= 15.

Pero es imposible extraer de K6una copia monocrom´atica de Gcon el primer color, o una copia

monocrom´

tica de H1con el segundo color, o una copia monocrom´atica de H2con el tercer color.

N´otese que la secuencia de coloraci´on m´as cr´ıtica en el presente ejemplo es

(0,0,0,0,0,1,1,1,1,1,2,2,2,2,2)

pues distribuye de forma uniforme y sim´etrica el n´umero de veces que aparece cada color en la

secuencia. Ahora, al disminuir en una unidad el n´umero de veces que aparece el tercer color en

la secuencia se elimina la posibilidad de extraer de K6una copia monocrom´atica de H2con el

tercer color, o al aumentar en una unidad el numero de veces que aparece el primer color permite

extraer de K6una copia monocrom´atica de Gcon el primer color. Sin embargo, al disminuir en

una unidad el tercer color y aumentar en una unidad el segundo color se obtiene una secuencia

con cuya coloraci´on no es posible extraer de K6una copia monocrom´atica de Gcon el primer

color, o una copia monocrom´

tica de H1con el segundo color, o una copia monocrom´atica de H2

con el tercer color. Por tanto, al tomar la secuencia

(0,0,0,0,0,1,1,1,1,1,1,2,2,2,2)

se tiene que no se pueden extraer las copias antes mencionadas.

Dada la observaci´on anterior se puede inferir que una condici´on suﬁciente para que se pueda

extraer de K6una copia monocrom´atica Gcon el primer color, o una copia monocrom´atica de

H1con el segundo color, o copia monocrom´atica de H2con el tercer color, es que el n´umero de

aristas del grafo completo que se estudie sea mayor o igual que |E(G)|+|E(H1)|+|E(H2)|. Por

tal raz´on, se vuelve a incrementar el n´umero de v´ertices en uno, es decir, t+1 →t+2, obteniendo

as´ı un n´umero de 7v´ertices para formar el grafo completo K7. Luego, usando el Corolario 2.1

con t= 5, se tiene que el n´umero de lados de K7es

P(5 + 2) = |E(K7)|=52+ 3 ×5+2

2= 21 >19 = |E(G)|+|E(H1)|+|E(H2)|.

Ahora, aplicando el Corolario 2.2 se tiene que

Q(5) = P(5 + 2) + 2

2=P(7) + 2

2=23

2=23 ×22

2= 253.

Entonces existe una aplicaci´on

Υ : E(KR(G,H))→(si)253

i=1,

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

Los n´umeros Ramsey para tres grafos y tres colores 19

para cada si, con i= 1,· · · ,253.

s1= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)

s2= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1)

s3= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2)

s4= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1)

s5= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2)

s6= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2)

s7= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1)

s8= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2)

s9= (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2)

s10 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2)

s11 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1)

s12 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2)

s13 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,2)

s14 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,2)

s15 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2)

s16 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1)

s17 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,2)

s18 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2)

s19 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,2,2)

s20 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,2,2)

s21 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2)

s22 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1)

s23 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2)

s24 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2)

s25 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2)

s26 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,2,2,2)

s27 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,2,2,2)

s28 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2)

s29 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1)

s30 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2)

s31 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2)

s32 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,2)

s33 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,2)

s34 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,2,2,2,2)

s35 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,2,2,2,2)

s36 = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2)

s37 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1)

s38 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2)

s39 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2)

s40 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2)

s41 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2)

s42 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,2,2)

s43 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,2,2,2,2,2)

s44 = (0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,2,2,2,2,2)

s45 = (0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2)

s46 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1)

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

20 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

s47 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2)

s48 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2)

s49 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2)

s50 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2)

s51 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,2)

s52 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,2,2,2)

s53 = (0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,2,2,2,2,2,2)

s54 = (0,0,0,0,0,0,0,0,0,0,0,0,1,2,2,2,2,2,2,2,2)

s55 = (0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2)

s56 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1)

s57 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2)

s58 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2)

s59 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2)

s60 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2)

s61 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2)

s62 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,2,2)

s63 = (0,0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2)

s64 = (0,0,0,0,0,0,0,0,0,0,0,1,1,2,2,2,2,2,2,2,2)

s65 = (0,0,0,0,0,0,0,0,0,0,0,1,2,2,2,2,2,2,2,2,2)

s66 = (0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2)

s67 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1)

s68 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2)

s69 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2)

s70 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2)

s71 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2)

s72 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2)

s73 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,2)

s74 = (0,0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2)

s75 = (0,0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2)

s76 = (0,0,0,0,0,0,0,0,0,0,1,1,2,2,2,2,2,2,2,2,2)

s77 = (0,0,0,0,0,0,0,0,0,0,1,2,2,2,2,2,2,2,2,2,2)

s78 = (0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2)

s79 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1)

s80 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2)

s81 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2)

s82 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2)

s83 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2)

s84 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2)

s85 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2)

s86 = (0,0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,2,2)

s87 = (0,0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2)

s88 = (0,0,0,0,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,2)

s89 = (0,0,0,0,0,0,0,0,0,1,1,2,2,2,2,2,2,2,2,2,2)

s90 = (0,0,0,0,0,0,0,0,0,1,2,2,2,2,2,2,2,2,2,2,2)

s91 = (0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2)

s92 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1)

s93 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2)

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

Los n´umeros Ramsey para tres grafos y tres colores 21

s94 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2)

s95 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2)

s96 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2)

s97 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2)

s98 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2)

s99 = (0,0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2)

s100 = (0,0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,2,2,2)

s101 = (0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2)

s102 = (0,0,0,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,2,2)

s103 = (0,0,0,0,0,0,0,0,1,1,2,2,2,2,2,2,2,2,2,2,2)

s104 = (0,0,0,0,0,0,0,0,1,2,2,2,2,2,2,2,2,2,2,2,2)

s105 = (0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2)

s106 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s107 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s108 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

s109 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

s110 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s111 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s112 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s113 = (0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s114 = (0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s115 = (0,0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s116 = (0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s117 = (0,0,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s118 = (0,0,0,0,0,0,0,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s119 = (0,0,0,0,0,0,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s120 = (0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s121 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s122 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s123 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

s124 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

s125 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s126 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s127 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s128 = (0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s129 = (0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s130 = (0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s131 = (0,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s132 = (0,0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s133 = (0,0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s134 = (0,0,0,0,0,0,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s135 = (0,0,0,0,0,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s136 = (0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s137 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s138 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s139 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

s140 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

22 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

s141 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s142 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s143 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s144 = (0,0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s145 = (0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s146 = (0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s147 = (0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s148 = (0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s149 = (0,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s150 = (0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s151 = (0,0,0,0,0,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s152 = (0,0,0,0,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s153 = (0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s154 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s155 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s156 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

s157 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

s158 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s159 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s160 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s161 = (0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s162 = (0,0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s163 = (0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s164 = (0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s165 = (0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s166 = (0,0,0,0,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s167 = (0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s168 = (0,0,0,0,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s169 = (0,0,0,0,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s170 = (0,0,0,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s171 = (0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s172 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s173 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s174 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

s175 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

s176 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s177 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s178 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s179 = (0,0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s180 = (0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s181 = (0,0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s182 = (0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s183 = (0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s184 = (0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s185 = (0,0,0,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s186 = (0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s187 = (0,0,0,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

Los n´umeros Ramsey para tres grafos y tres colores 23

s188 = (0,0,0,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s189 = (0,0,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s190 = (0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s191 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s192 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s193 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

s194 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

s195 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s196 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s197 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s198 = (0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s199 = (0,0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s200 = (0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s201 = (0,0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s202 = (0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s203 = (0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s204 = (0,0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s205 = (0,0,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s206 = (0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s207 = (0,0,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s208 = (0,0,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s209 = (0,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s210 = (0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s211 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s212 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s213 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

s214 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

s215 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s216 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s217 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s218 = (0,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s219 = (0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s220 = (0,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s221 = (0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s222 = (0,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s223 = (0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s224 = (0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s225 = (0,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s226 = (0,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s227 = (0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s228 = (0,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s229 = (0,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s230 = (0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s231 = (0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s232 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)

s233 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2)

s234 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2)

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

24 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

s235 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2)

s236 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2)

s237 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2)

s238 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2)

s239 = (1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2)

s240 = (1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2)

s241 = (1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2)

s242 = (1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2)

s243 = (1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2)

s244 = (1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2)

s245 = (1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2)

s246 = (1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s247 = (1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s248 = (1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s249 = (1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s250 = (1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s251 = (1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s252 = (1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

s253 = (2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)

Figura 1: K7coloreado con la secuencia s111 y los subgrafos Ψ, Ψ1y Ψ2.

Por ejemplo, consid´ere la secuencia S111 para colorear arbitrariamente los lados del grafo

completo K7, entonces hay una coloraci´on tal que existe una terna de grafos (Ψ,Ψ1,Ψ2)donde

se cumple que K7= Ψ ∪Ψ1∪Ψ2y se puede extraer de Ψuna copia monocrom´atica G0isomorfa

aGcon el primer color, o extraer de Ψ1una copia monocrom´atica H0

1de H1con el segundo

color, o extraer de Ψ2una copia monocrom´atica H0

2de H2con el tercer color. N´otese, que de Ψ

se puede extraer una copia monocrom´atica G0isomorfa a G, como se observa en la Figura 1.

Finalmente, al colorear los lados del menor grafo completo KR(G,H1,H2)con cada secuencia

si, para todo i= 1,· · · ,253, siempre existe una coloraci´on en la cual es posible extraer de Ψuna

copia monocrom´atica G0de G, o de Ψ1una copia monocrom´atica H0

1de H1, o de Ψ2una copia

monocrom´atica H0

2de H2. Por lo tanto, R(G, H1, H2)=7, con t= 5,n= 4, para 3grafos y 3

colores.

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

Los n´umeros Ramsey para tres grafos y tres colores 25

El conjunto de valores obtenidos en el Cuadro 1, provienen de haber resuelto una variada

cantidad de ejemplos que dieron como resultado un conjunto de patrones de los n´umeros de

Ramsey para tres grafos y tres colores. Este conjunto de patrones obtenidos en el Cuadro 1,

satisfacen para tres grafos cualequiera, simple, ﬁnitos, no vac´ıos, que solo van a depender del

n´umero de v´ertices y de tres colores diferentes.

n≥4t≥5G=KnH1=WnR(G, H1, K4−l)|E(Kt+2)| {si}Q(t)

i=1

n= 4 t= 5 K4W47 21 253

n= 5 t= 6 K5W58 28 435

n= 6 t= 7 K6W69 36 703

n= 7 t= 8 K7W710 45 1081

n t KnWnt+ 2 t2+3t+2

(t2+3t+6)(t2+3t+4)

Cuadro 1: Patr´on obtenido de los n´umeros Ramsey para los grafos Kn,Wn, y D4.

4 Resultado principal

El siguiente resultado es un caso general, para tres grafos cualesquiera, simples, ﬁnitos, no vac´ıos

y tres colores diferentes.

Teorema 4.1. Sean n≥4,Knun grafo completo, Wnun garfo rueda, y D4grafos diamante.

Sean {0,1,2}tres colores diferentes; t=m´ax{|Kn|,|Wn|,|D4|};P(t) = t2−t

2;Q(t) = P(t)+2

2;

y{si}Q(t)

i=1 el conjunto de las secuencias formadas con los tres colores como en la Deﬁnici´on 2.4,

entonces R(Kn, Wn, D4) = t+ 2, para t≥5.

Demostraci´on. Sean Kn,Wn, y D4los grafos dados. T´omese t= m´ax{|Kn|,|Wn|,|D4|}, as´ı t=

n+ 1 y def´ınanse los polinomios

P(t) = t

2=t2−t

2yQ(t) = P(t)+2

2=t4+ 6t3+ 19t2+ 30t+ 24

23.

Por otro lado, sean {0,1,2}tres colores diferentes y W={si}Q(t)

i=1 el conjunto de secuencias

construidas como en la Deﬁnici´on 2.4 con las cuales se realizar´an las coloraciones de los grafos

que se estudiar´an.

Sup´ongase ahora que R(Kn, Wn, D4) = t+ 1, entonces por la Deﬁnici´on 2.5 existe una terna

(Ψ,Ψ1,Ψ2) tal que

(i) Ψ = Ψ1∪Ψ2.

(ii) El grafo completo Kt+1 es la superposici´on de Ψ.

(iii) |V(Kt+1)|=|V(Ψ)|=|V(Ψ1)|=|V(Ψ2)|.

(iv) E(Ψ1)∩E(Ψ2) = ∅.

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

26 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

(v) El grafo Ψ contiene una copia monocrom´atica G0de Kno de Ψ1puede extraerse una copia

monocrom´atica H0

1de Wno de Ψ2puede extraerse una copia monocrom´atica H0

2de D4.

N´otese que si |E(Kt+1)|<|E(Kn)|+|E(Wn)|+|E(D4)|, por los ´ıtem (i), (ii), y (iv), se tiene

que

|E(Ψ)|+|E(Ψ1)|+|E(Ψ2)|<|E(Kn)|+|E(Wn)|+|E(D4)|(4.1)

pues |E(Kt+1)|=|E(Ψ)|+|E(Ψ1)|+|E(Ψ2)|. Luego, por el ´ıtem (v) se tendr´ıa que |E(Ψ)|<

|E(Kn)|o|E(Ψ1)|<|E(Wn)|oE(Ψ2)|<|E(D4)|. Sin p´erdida de generalidad, se puede suponer

que |E(Ψ)|<|E(Kn)|. De donde, usando la ecuaci´on (4.1), se obtiene que

|E(Ψ1)|+|E(Ψ2)|<|E(Wn)|+|E(D4)|(4.2)

En este punto, por el mismo ´ıtem (v), se tendr´ıa que |E(Ψ1)|<|E(Wn)|oE(Ψ2)|<|E(D4)|.

De forma similar, y sin p´erdida de generalidad, se puede suponer que

|E(Ψ1)|<|E(Wn)|(4.3)

As´ı, de las ecuaciones (4.1), (4.2) y (4.3), se tiene que

|E(Ψ)|<|E(Kn)| |E(Ψ1)|<|E(Wn)| |E(Ψ2)|<|E(D4)|(4.4)

Esto ´utlimo permite inferir claramente que no es posible extraer de Ψ una copia monocrom´atica

G0de Kn, o de Ψ1una copia monocrom´atica H0

1de Wn, o de Ψ2una copia monocrom´atica H0

de D4, lo cual es una contradicci´on a lo supuesto de inicio.

Ahora, como t=n+ 1 entonces n=t−1

|E(Kn)|=|E(Kt−1)|=(t−1)(t−2)

2|E(Wt−1)|= 2(t−2) |E(D4)|= 4 (4.5)

y por tanto

(t−1)(t−2)

2+2(t−2)+4 = (t2−3t+ 2) + 4(t−2) + 8

2=t2+t+ 2

2=t(t+ 1)

2+1 >|E(Kt+1)|

ya que t≥5. Luego, por lo demostrado anteriormente se tendr´ıa que R(Kn, Wn, D4)> t + 1.

Proc´edase a aumentar el valor de t+ 1 en una unidad (t+ 1 →t+ 2), para formar el grafo

completo Kt+2 cuyos lados ser´an coloreados con las secuencias si∈W. Luego, por hip´otesis se

tiene que |E(D4)|= 4 < t de donde:

(t−1)(t−2)

2+ 2(t−2) + |E(D4)|<t2+ 3t−6

Usando las ecuaciones (4.5) se obtiene que

|E(Kn)|+|E(Wn)|+|E(D4)|<t2+ 3t−6

2<t2+ 3t+ 2

2=|E(Kt+2)|(4.6)

Ahora, si se representan por Ci(Kt+2) al conjunto de lados coloreados con el color i, para

i= 0,1,2. Se obtiene, usando la ecuaci´on (4.6), que las coloraciones del grafo completo Kt+2 se

pueden dividir en varios grupos:

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

Los n´umeros Ramsey para tres grafos y tres colores 27

• |Ci(Kt+2)|≥|E(Kn)|.

• |Ci(Kt+2)|<|E(Kn)|y|Ci(Kt+2)| ≥ |E(Wn)|.

• |Ci(Kt+2)|<|E(Kn)|y|Ci(Kt+2)|<|E(Wn)|y|Ci(Kt+2)|≥|E(D4)|.

para i= 0,1,2.

Sup´ongase ahora que se colorea el grafo Kt+2 con una secuencia sj∈Wtal que

|Ci(Kt+2)|≥|E(Kn)|

Aqu´ı, se hace Ψ al subgrafo monocrom´atico de Kt+2 coloreado con el color ital que |V(Ψ)|=

|V(Kt+2)|. Como |E(Ψ) ≥ |E(Kn)|, y dado que Kt+2 es conexo, entonces se puede extraer de Ψ

un subgrafo G0conexo monocrom´atico isomorfo a Kn, para i= 0,1,2. Luego, al colorear los lados

de Kt+2, con las secuencias sjdadas, existe por las deﬁniciones 2.7 y 2.6, una funci´on biyectiva

ϕque cumple que

ϕ:V(G

0)→V(Kn); uavb∈E(G

0)⇔ϕ(ua)ϕ(vb) = wawb∈E(Kn).

Si se colorea el grafo Kt+2 con una secuencia sj∈Wtal que |Ci(Kt+2)|<|E(Kn)|y

|Ci(Kt+2)| ≥ |E(Wn)|, para i= 0,1,2, entonces se hace Ψ1al subgrafo monocrom´atico de Kt+2

coloreado con el color ital que |V(Ψ1)|=|V(Kt+2)|. Como |E(Ψ1)≥ |E(Wn)|, y dado que Kt+2

es conexo, entonces se puede extraer de Ψ1un subgrafo H0

1conexo monocrom´atico isomorfo a

Wn. Luego, al colorear los lados de Kt+2 con las secuencias sjdadas, existe por las deﬁniciones

2.7 y 2.6, una funci´on biyectiva ϕque cumple que

ϕ:V(H0

1)→V(Wn); ucvd∈E(H0

1)⇔ϕ(vc)ϕ(vd) = ycyd∈E(Wn).

Por ´ultimo, si se colorea el grafo Kt+2 con una secuencia sj∈Wtal que

|Ci(Kt+2)|<|E(G)|y|Ci(Kt+2)|<|E(H1)|y|Ci(Kt+2)| ≥ |E(H2)|

para i= 0,1,2, entonces se hace Ψ2al subgrafo monocrom´atico de Kt+2 coloreado con el color

i. Como |E(Ψ2)≥ |E(D4)|, y dado que Kt+2 es conexo, entonces se puede extraer de Ψ2un

subgrafo H0

2conexo monocrom´atico isomorfo a Wn. Luego, al colorear los lados de Kt+2 con las

secuencias sjdadas, existe por las deﬁniciones 2.7 y 2.6, una funci´on biyectiva ϕque cumple que

ϕ:V(H0

2)→V(D4); uevf∈E(H

2)⇔ϕ(ue)ϕ(vf) = zezf∈E(D4).

Cumpli´endose que Ges bueno con respecto a H, es decir, existe el grafo completo

Kt+2 = Ψ ∪Ψ1∪Ψ2

tal que de Ψ se pueda extraer una copia monocrom´atica G0de Kn, o de Ψ1pueda extraer

una copia monocrom´atica H0

1de Wno Ψ2pueda extraer una copia monocrom´atica H0

2de D4,

tendiendo entonces que R(Kn, Wn, D4) = t+ 2, para t≥5.

5 Dedicatoria

Esta publicaci´on est´a dedicada al profesor Jos´e Rafael Figueroa quien no pudo ver concretada

la publicaci´on de este art´ıculo, estudio que realiz´aramos conjuntamente durante el a˜no 2022, del

cual existe una continuaci´on inconclusa. Gracias Jos´e por ser un gran colega y amigo, prometemos

terminar y publicar en tu memoria (incluy´endote como autor) los trabajos que hab´ıamos inciado

en conjunto durante los a˜nos 2022 y 2023. Ilumina nuestro entendimiento desde donde est´es.

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28

28 Jos´e Figueroa - Tob´ıas Rosas - Henry Ram´ırez - Armando Anselmi

Referencias

[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¨os P. (1984) “Generalizations of a Ramsey theoretic result of Chvatal”,

Journal of Graph Theory 7: 39–51.

[3] Camacho D.J.A. Teorema del ´

Indice de Poincar´e, 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´atal and F. Harary, Generalized Ramsey theory for graphs, III:small oﬀ- diagonal

numbers, Paciﬁc Journal of Mathematics, 41 (1972), 335-345.

[6] P. Erd¨os, Some remarks on the theory of graphs Bull. Amer. Math. Soc. 53 (1947), 292-294.

[7] P. Erd¨os and G. Szekeres, On a combinatorial problem in geometry, Composition Mathema-

tica 2(1935), 463-470.

[8] J. Figueroa; F. Villarroel; H. Ramirez y J. Otero, Los N´umeros de Ramsey con componente

h−buena y secuencias sim´etricas, Divulgaciones Matem´aticas, No 1 20(2019), 78-90.

[9] Radziszowski S.P. and Xia J. (1994) “Paths, cycles and wheels in graphs without antitrian-

gles”, Australasion Journal of Combinatorics 9, 221-232.

[10] Surahmat and Baskoro E.T. (2001) “On the Ramsey Number of Path or Star versus W4or

W5”, Proc. Twelfth Autraslasian Workshop on Combinatorial Algorithms, Bandung, Indo-

nesia, 14-17 July, 174-179.

[11] Villaroel F.; Figueroa J.; Marquez H. and Anselmi A. Un m´etodo algor´ıtmico para el calculo

del n´umero Baric´entrico 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.

Divulgaciones Matem´aticas Vol. 23-24, No. 1-2 (2022-2023), pp. 12–28