Geodesic
Three color Ramsey numbers for graphs with at most 4 vertices
Luis Boza1 ; Janusz Dybizbański2 ; Tomasz Dzido2
1University of Sevilla
2University of Gda´nsk
The electronic journal of combinatorics, Tome 19 (2012) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

For given graphs $H_{1}, H_{2}, H_{3}$, the 3-color Ramsey number $R(H_{1},$ $H_{2}, H_{3})$ is the smallest integer $n$ such that if we arbitrarily color the edges of the complete graph of order $n$ with $3$ colors, then it always contains a monochromatic copy of $H_{i}$ colored with $i$, for some $1 \leq i \leq 3$.We study the bounds on 3-color Ramsey numbers $R(H_1,H_2,H_3)$, where $H_i$ is an isolate-free graph different from $K_2$ with at most four vertices, establishing that $R(P_4,C_4,K_4)=14$, $R(C_4,K_3,K_4-e)=17$, $R(C_4,K_3+e,K_4-e)=17$, $R(C_4,K_4-e,K_4-e)=19$, $28\le R(C_4,K_4-e,K_4)\le36$, $R(K_3,K_4-e,K_4)\le41$, $R(K_4-e,K_4-e,K_4)\le59$ and $R(K_4-e,K_4,K_4)\le113$. Also, we prove that $R(K_3+e,K_4-e,K_4-e)=R(K_3,K_4-e,K_4-e)$, $R(C_4,K_3+e,K_4)\le\max\{R(C_4,K_3,K_4),29\}\le32$, $R(K_3+e,K_4-e,K_4)\le\max\{R(K_3,K_4-e,K_4),33\}\le41$ and $R(K_3+e,K_4,K_4)\le\max\{R(K_3,K_4,K_4),2R(K_3,K_3,K_4)+2\}\le79$.This paper is an extension of the article by Arste, Klamroth, Mengersen [Utilitas Mathematica, 1996].
DOI : 10.37236/2160
Classification : 05C55, 05D10, 05C35
Mots-clés : extremal graphs, Ramsey numbers

Luis Boza  1   ; Janusz Dybizbański  2   ; Tomasz Dzido  2

1 University of Sevilla
2 University of Gda´nsk 
@article{10_37236_2160,
     author = {Luis Boza and Janusz Dybizba\'nski and Tomasz Dzido},
     title = {Three color {Ramsey} numbers for graphs with at most 4 vertices},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {4},
     doi = {10.37236/2160},
     zbl = {1266.05085},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2160/}
}
TY  - JOUR
AU  - Luis Boza
AU  - Janusz Dybizbański
AU  - Tomasz Dzido
TI  - Three color Ramsey numbers for graphs with at most 4 vertices
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2160/
DO  - 10.37236/2160
ID  - 10_37236_2160
ER  - 
%0 Journal Article
%A Luis Boza
%A Janusz Dybizbański
%A Tomasz Dzido
%T Three color Ramsey numbers for graphs with at most 4 vertices
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2160/
%R 10.37236/2160
%F 10_37236_2160
Luis Boza; Janusz Dybizbański; Tomasz Dzido. Three color Ramsey numbers for graphs with at most 4 vertices. The electronic journal of combinatorics, Tome 19 (2012) no. 4. doi: 10.37236/2160

Cité par Sources :