Geodesic
On Monochromatic Subgraphs of Edge-Colored Complete Graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 5-22.

Voir la notice de l'article provenant de la source Library of Science

In a red-blue coloring of a nonempty graph, every edge is colored red or blue. If the resulting edge-colored graph contains a nonempty subgraph G without isolated vertices every edge of which is colored the same, then G is said to be monochromatic. For two nonempty graphs G and H without isolated vertices, the monochromatic Ramsey number mr(G,H) of G and H is the minimum integer n such that every red-blue coloring of Kn results in a monochromatic G or a monochromatic H. Thus, the standard Ramsey number of G and H is bounded below by mr(G,H). The monochromatic Ramsey numbers of graphs belonging to some common classes of graphs are studied. We also investigate another concept closely related to the standard Ramsey numbers and monochromatic Ramsey numbers of graphs. For a fixed integer n ≥ 3, consider a nonempty subgraph G of order at most n containing no isolated vertices. Then G is a common monochromatic subgraph of Kn if every red-blue coloring of Kn results in a monochromatic copy of G. Furthermore, G is a maximal common monochromatic subgraph of Kn if G is a common monochromatic subgraph of Kn that is not a proper subgraph of any common monochromatic subgraph of Kn. Let S(n) and S*(n) be the sets of common monochromatic subgraphs and maximal common monochromatic subgraphs of Kn, respectively. Thus, G ∈ S(n) if and only if R(G,G) = mr(G,G) ≤ n. We determine the sets S(n) and S*(n) for 3 ≤ n ≤ 8.
Keywords: Ramsey number, monochromatic Ramsey number, common monochromatic subgraph, maximal common monochromatic subgraph 
@article{DMGT_2014_34_1_a0,
     author = {Andrews, Eric and Fujie, Futaba and Kolasinski, Kyle and Lumduanhom, Chira and Yusko, Adam},
     title = {On {Monochromatic} {Subgraphs} of {Edge-Colored} {Complete} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--22},
     publisher = {mathdoc},
     volume = {34},
     number = {1},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a0/}
}
TY  - JOUR
AU  - Andrews, Eric
AU  - Fujie, Futaba
AU  - Kolasinski, Kyle
AU  - Lumduanhom, Chira
AU  - Yusko, Adam
TI  - On Monochromatic Subgraphs of Edge-Colored Complete Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 5
EP  - 22
VL  - 34
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a0/
LA  - en
ID  - DMGT_2014_34_1_a0
ER  - 
%0 Journal Article
%A Andrews, Eric
%A Fujie, Futaba
%A Kolasinski, Kyle
%A Lumduanhom, Chira
%A Yusko, Adam
%T On Monochromatic Subgraphs of Edge-Colored Complete Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 5-22
%V 34
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a0/
%G en
%F DMGT_2014_34_1_a0
Andrews, Eric; Fujie, Futaba; Kolasinski, Kyle; Lumduanhom, Chira; Yusko, Adam. On Monochromatic Subgraphs of Edge-Colored Complete Graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 5-22. http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a0/

[1] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (Chapman and Hall/CRC, Boca Raton, FL., 2010).

[2] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2011) DS1.