On Monochromatic Subgraphs of Edge-Colored Complete Graphs

Eric Andrews, et al. "On Monochromatic Subgraphs of Edge-Colored Complete Graphs." Discussiones Mathematicae Graph Theory 34.1 (2014): 5-22. <http://eudml.org/doc/268028>.

@article{EricAndrews2014,
abstract = {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 mono- chromatic 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 Ram- sey numbers and monochromatic Ramsey numbers of graphs. For a fixed integer n ≥ 3, consider a nonempty subgraph G of order at most n con- taining 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 sub- graph 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.},
author = {Eric Andrews, Futaba Fujie, Kyle Kolasinski, Chira Lumduanhom, Adam Yusko},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ramsey number; monochromatic Ramsey number; common monochromatic subgraph; maximal common monochromatic subgraph},
language = {eng},
number = {1},
pages = {5-22},
title = {On Monochromatic Subgraphs of Edge-Colored Complete Graphs},
url = {http://eudml.org/doc/268028},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Eric Andrews
AU - Futaba Fujie
AU - Kyle Kolasinski
AU - Chira Lumduanhom
AU - Adam Yusko
TI - On Monochromatic Subgraphs of Edge-Colored Complete Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 5
EP - 22
AB - 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 mono- chromatic 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 Ram- sey numbers and monochromatic Ramsey numbers of graphs. For a fixed integer n ≥ 3, consider a nonempty subgraph G of order at most n con- taining 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 sub- graph 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.
LA - eng
KW - Ramsey number; monochromatic Ramsey number; common monochromatic subgraph; maximal common monochromatic subgraph
UR - http://eudml.org/doc/268028
ER -